KMP算法实现 |单模字符串匹配

导读： 文章浏览阅读199次。写在前面KMP算法是经典的单模字符串匹配算法。当模式串和主串已经匹配一部分的情况下失配时，暴力匹配采取的是，回溯主串和模式串的指针...

写在前面

KMP算法是经典的单模字符串匹配算法。当模式串和主串已经匹配一部分的情况下失配时，暴力匹配采取的是，回溯主串和模式串的指针，使其达到模式串相对于主串向后移动一位的效果，因为原主串和模式串已经部分匹配成功，此处仅向后挪动一位的从头匹配，相当于模式串自己和自己错位匹配，暴力算法主要浪费时间就在此处。KMP算法解决的就是这个问题，先让模式串自己与自己错位匹配，大概率是匹配失败的，KMP算法找到能够使模式串与自己的错位匹配能够成功的并且不漏掉信息的最长的移动距离。将之存储在next表中，故而关键是维护next表。

如果next[i]存储数字是j，则表示，当模式串在i处失配时，将保证主串的指针不变，将模式串的指针指向j，就可以实现当模式串S1第i位与S2的第j位对齐时（S1=S2），S2的j位前侧的不包括空格的字符与对应的S1字符串中的i位前侧的字符是匹配的。

详细讲解以后补充，代码如下。

KMP匹配实现

需要说明的是，QString即为QT之中封装的字符串类。

int countWordsFKMP(const QString &paragraph, const QString &word)
{
    //统计paragraph中 word出现的频率，（注意：不回溯主串指针）
    int count=0;//统计字符串出现的频率
    int pLen=paragraph.length();//文章长度
    int wLen=word.length();//单词长度
    int* next=new int(wLen);//next数组
    countWordsFKMPFail(word,next);
    for(int i=0,j=0;i<pLen;)
    {
        if(paragraph[i]==word[j])
        {
            i++;
            j++;
            if(j==wLen)
            {
                //当全部匹配成功时,计数+1，并将模式串指针归零
                count++;
                j=0;
            }
        }
        else
        {
            if(j==0)
            {
                //第一个就不匹配，主串指针挪一位
                i++;
            }
            else
            {
                //匹配途中不匹配，寻找对齐点
                j=F[j-1]+1;
            }
        }
    }
    delete [] next;
    return count;
}

失配函数/next表计算

void MainWindow::countWordsFKMPFail(const QString &word, int F[])
{
    //计算失配函数F(x)
    int len=word.length();
    F[0]=-1;
    for(int i=1;i<len;i++)
    {
        int j=next[i-1];
        while (word[j+1]!=word[i]&&j>=0) {
            j=next[j];
        }
        if(word[j+1]==word[i])
        {
            next[i]=j+1;
        }
        else
        {
            next[i]=-1;
        }
    }
    return;
}