算法 kmp算法-蒲公英云

kmp算法是改进后的字符匹配算法，它与bf算法的区别是，每次从串与主串匹配失败后，从串与主串匹配的位置不同。

下面具体说下这两种算法的区别：

主串：BABCDABABCDABCED

从串：ABCDABCED

BF算法：

第一步：

从主串的第一个字符位置开始与从串第一个字符位置进行匹配，匹配失败

第二步：

从主串的第二个字符位置开始与从串第一个字符位置进行匹配，匹配失败

第三步：

从主串的第三个字符位置开始与从串第一个字符位置进行匹配，匹配失败

………..

第七步：

从主串的第七个字符位置开始于从串第一个字符位置进行匹配，匹配失败

第八步：

匹配成功，这个就是BF算法，每次匹配失败后要从主串的下一个字符位置与从串的第一个字符接着进行匹配。

kmp算法：

第一步：

主串与从串的第一个字符不匹配

第二步：

这两步和bf一样

第三步：

这里就和bf不一样了，其原因就是从串中字符有相同的一部分（AB），这里先知道区别，待会我会说它的实现过程

第四步：

如果看不懂的话，下面会讲清楚，然后根据程序找下标就可以知道原因了。

kmp算法分两部分：①next数组（kmp算法的核心）

②字符串的匹配

在讲解next数组时，顺便把前缀和后缀的知识也说了。

比如上面的从串：ABCDABCED（前缀是从第一个字符数，但后缀不是倒着数，它也是顺着数，看下面的写法吧）

第一个字符前，它没有串，所以没有前缀和后缀，则它也没有最长长度，我把它的长度初始化为0。

第二个字符前，它的串是A，前缀和后缀是不能包含串本身，所以它没有前缀和后缀，长度为0。

第三个字符前，它的串是AB，前缀是A，后缀是B，不匹配，长度为0。

第四个字符前，它的串是ABC，第一种，前缀是A，后缀是C，不匹配，长度为0，

第二种，前缀是AB，后缀是BC，不匹配，长度为0，

所以最长长度为0。

第五个字符前，它的串是ABCD，第一种，前缀是A，后缀是D，不匹配，长度为0，

第二种，前缀是AB，后缀是CD，不匹配，长度为0，

第三种，前缀是ABC，后缀是BCD，不匹配，长度为0，

所以最长长度为0。

第六个字符前，它的串是ABCDA，第一种，前缀是A，后缀是A，匹配，长度为1，

第二种，前缀是AB，后缀是DA，不匹配，长度为0，

第三种，前缀是ABC，后缀是CDA，不匹配，长度为0，

第四种，前缀是ABCD，后缀是BCDA，不匹配，长度为0，

所以最长长度为1。

第七个字符前，它的串是ABCDAB，第一种，前缀是A，后缀是B，不匹配，长度为0，

第二种，前缀是AB，后缀是AB，匹配，长度为2，

第三种，前缀是ABC，后缀是DAB，不匹配，长度为0，

第四种，前缀是ABCD，后缀是CDAB，不匹配，长度为0，

第五种，前缀是ABCDA，后缀是BCDAB，不匹配，长度为0，

所以最长长度为2。

第八个字符前，它的串是ABCDABC，第一种，前缀是A，后缀是C，不匹配，长度为0，

第二种，前缀是AB，后缀是BC，不匹配，长度为0，

第三种，前缀是ABC，后缀是ABC，匹配，长度为3,

第四种，前缀是ABCD，后缀是DABC，不匹配，长度为0，

第五种，前缀是ABCDA，后缀是CDABC，不匹配，长度为0，

第六种，前缀是ABCDAB，后缀是BCDABC，不匹配，长度为0，

所以最长长度为3。

第九个字符前，它的串是ABCDABCE，第一种，前缀是A，后缀是E，不匹配，长度为0，

第二种，前缀是AB，后缀是CE，不匹配，长度为0，

第三种，前缀是ABC，后缀是BCE，不匹配，长度为0,

第四种，前缀是ABCD，后缀是ABCE，不匹配，长度为0，

第五种，前缀是ABCDA，后缀是DABCE，不匹配，长度为0，

第六种，前缀是ABCDAB，后缀是CDABCE，不匹配，长度为0，

第七种，前缀是ABCDABC，后缀是BCDABCE，不匹配，长度为0，

所以最长长度为0。

然后根据我们求出来的最长长度，就能绘制出next表了，

下标	1	2	3	4	5	6	7	8	9
从串	A	B	C	D	A	B	C	E	D
next	0	0	0	0	0	1	2	3	0

可能别人的next和kmp和我写的不一样，不过我就是这么理解的，如果哪里错了，大家可以提出来

当然这个next数组也可以改进的，大家想一想，上面在比较bf与kmp算法是，kmp的第三步是不是多余了，为什么呢，因为第二步的ABCDABC中的第二个C与主串中的A不匹配，第三步还是ABC，这里面的C肯定也与A不匹配，所以也就有了next数组的改进，怎么改进呢，很简单，只要相等时候，让它等于前面那个一样字符的next数组下标就可以了，看表格

下标	1	2	3	4	5	6	7	8	9
从串	A	B	C	D	A	B	C	E	D
next	0	0	0	0	0	0	0	3	0

第二个B与第一个B的next值一样为0，第二个C与第一个C的next值一样为0。

这就是next数组及其改进后的next数组。

next数组程序：

void Get_next(int *next, string s2)
{
    int i = 1;
    int j = 0;
    next[i] = 0;
    while(i <= s2.length())
    {
        if(j == 0 || s2[i - 1] == s2[j - 1])
        {
            i++;
            j++;
            if(s2[i - 1] == s2[j - 1])
                next[i] = next[j];
            else
                next[i] = j - 1;
        }
        else
            j = next[j];
    }
}

如果你理解了next数组的求值方法，根据bf算法的思路应该可以写出kmp字符匹配函数，

下面是kmp算法的总体程序：

#include <iostream>
#include <string>
using namespace std;
//求next数组下标
void Get_next(int *next, string s2)
{
    int i = 1;
    int j = 0;
    next[i] = 0;
    while(i <= s2.length())
    {
        if(j == 0 || s2[i - 1] == s2[j - 1])
        {
            i++;
            j++;
            if(s2[i - 1] == s2[j - 1])
                next[i] = next[j];
            else
                next[i] = j - 1;
        }
        else
            j = next[j];
    }
//    for(int k = 1; k < 10; k++)
//        cout << next[k] << endl;
}
//匹配部分
int kmp(string s1, string s2, int pos)
{
    int next[100];
    Get_next(next, s2);
    int i = 0;
    int j = 0;
    while(i < s1.length() && j < s2.length())
    {
        if(j == 0 || s1[i] == s2[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j + 1];
        }
    }
    if(j >= s2.length())
        return i - s2.length();
    return -1;
}
int main()
{
    string s1= "babcdababcdabced";
    string s2 = "abcdabced";
    int pos;
    cin >> pos;
    cout << kmp(s1, s2 ,pos) << endl;
    return 0;
}