这位dalao讲的太好了一看就懂！！

借鉴原博注意

因为当年学KMP时过于蒟蒻什么都不懂结果到现在什么都不懂有重新学一遍真是丢人

KMP的意义及作用

简单来说KMP就是为了节省在暴力模拟匹配时不必要走的循环次数
也就是节省不必要的匹配
例如：

$A=abbaabbbabaa$
$B=abbaaba$

首先定义两个指针，i=0，j=0开始扫
在这个例子中，我们依然从第1位开始匹配，直到匹配失败：

———-i=6

$abbaab$$\color{Red}{b}$
$babba$

———-j=6

$abbaab$$\color{Red}{a}$

当我们发现第7位不匹配
那么我们若按照原来的方式继续匹配，则是把B串向后移一位，重新从第一个字符开始匹配

–i=1

$a$$\color{Red}{b}$$baabbbabba$

j=0

$\color{Red}{a}$$bbaaba$

依然不匹配，那我们就要继续往后移咯。
且住！
既然我们已经匹配了前面的6位，那么我们也就知道了A串这6位和B串的前6位是匹配的，我们能否利用这个信息来优化我们的匹配呢？
也就是说，我们能不能在上面匹配失败后直接跳到：

—–i=5

$abb$$\color{Red}{a}$$bbbabaa$

-j=1

$\color{Red}{a}$$bbaaba$

这样就可以省去很多不必要的匹配。
这时候next数组就诞生了！！

前缀：指的是字符串的子串中从原串最前面开始的子串，如$abcdef$的前缀有：$a,ab,abc,abcd,abcde$
后缀：指的是字符串的子串中在原串结尾处结尾的子串，如$abcdef$的后缀有：$f,ef,def,cdef,bcdef$
KMP算法引入了一个next数组，$next[i]$表示的是前i的字符组成的这个子串最长的相同前缀后缀的长度！
怎么理解呢？
例如字符串$aababaaba$的相同前缀后缀有$a$和$aaba$，那么其中最长的就是$aaba$。

KMP算法模拟过程

那么现在假设我们已经得到了next 的所有值，我们如何利用F数组求解呢？
我们还是先给出一个例子：
$A=abaabaabbabaaabaabbabaab$
$ B=abaabbabaab $

当然读者可以通过手动模拟得出只有一个地方匹配

$abaabaabbabaa$$\color{Red}{abaabbabaab}$

那么我们根据手动模拟，同样可以计算出各个next的值
$B= a b a a b b a b a a b $
next= 0 0 1 1 2 0 1 2 3 4 5
仍然是从i=0，j=0开始匹配

———i=5

$abaab$$\color{Red}{a}$$abbabaaabaabbabaab $

———j=5

$abaab$$\color{Red}{b}$$abaab$

发现不匹配，此时i=5,j=5，那么我们看next[j-1]的值：

next[5-1]=2;

于是j=next[i-1]=2

———————–i=13

$abaabaabbabaa$$\color{Red}{a}$$baabbabaab$

—————–j=10

$abaabbabaa$$\color{Red}{b}$

我们又发现，A串的第13位和B串的第10位不匹配，此时i=13,j=10，那么我们看next[j-1]的值

next[10-1]=4;

这说明B串的0~3位是与当前(i-4)~(i-1)是匹配的，我们就不需要重新再匹配这部分了，把B串向后移，从B串的第4位开始匹配：

于是j=next[i-1]=4;

···

以此类推最后我们会匹配成功

这就是next数组的用处

其实就是i一直往后扫，不会向前变动，只是j在匹配到不同字符时自动根据next数组进行适当调整，保证不会多不会少，刚好从需要的地方匹配

就是节省了后缀与前缀相同时的比较次数
因为A的前缀已经和B的前缀比较过了，
就相当于A字串此时与前缀相同的后缀已经和B字串的前缀比较过了，j就可以直接跳到相同前缀的后一位再继续比较
就节省了许多时间

next数组实现

代码

void getnext(string s)
{
    int l=s.length(),t;
    Next[0]=-1;
    for(int i=1;i<l;i++)
    {
        t=Next[i-1];
        while(s[t+1]!=s[i]&&t>=0)t= Next[t];
        if(s[t+1]==s[i])Next[i]=t+1;
        else Next[i]=-1;

    }
}

1.F[0]=-1　(虽说这里应该是０，但为了方便判越界，同时为了方便判断第０位与第i位，程序中这里置为-1)
2.这是一个从前往后的线性推导，所以在计算F[i]时可以保证F[0]~F[i-1]都是已经计算出来的了
3.若以某一位结尾的子串不存在相同的前缀和后缀，这个位的F置为-1（这里置为-1的原因同第一条一样）

重要！：另外，为了在程序中表示方便，在接下来的说明中，F[i]=0表示最长相同前缀后缀长度为１，即真实的最长相同前缀后缀＝F[i]+1。(重要的内容要放大)

为什么要这样设置呢，因为这时F[i]代表的就不仅仅与前后缀长度有关了，它还代表着这个前缀的最后一个字符在子串B中的位置

那么，我们同样可以推出，求解next的思路是：看next[i-1]这个最长相同前缀后缀的后面是否可以接i，若可以，则直接接上，若不可以，下面再说。
举个例子：
还是以$B=abaabbabaab$为例，我们看到第2个。
B= “a b a a b b a b a a b”
next=-1 -1
此时这个a的前一个b的F值为-1，所以此时a不能接在b的后面（b的相同最长前缀后缀是0啊），此时，j=-1，所以我们判断B[j+1]与B[2]，即B[0]与B[2]是否一样。
一样，所以next[2]=j+1=0（代表前0~2字符的最长相同前缀后缀的前缀结束处是B[0],长度为0+1=1）。

再来看到第3个：
B= “a b a a b b a b a a b”
next=-1 -1 0

B= “a b a a b b a b a a b”
next=-1 -1 0 0

j首先为next[4-1]=0，我们看到B[j+1=1]==B[i]，所以

next[i]=j+1=1。

再强调一遍，我们这样求出来的next值是该最长相同前缀后缀中的前缀的结束字符的数组位置（从0开始编号），如果要求最长相同前缀后缀的长度，要输出next[i]+1。

kmp匹配

直接上代码

void KMP(string a,string b)
{
    getnext(b);
    int lena=a.length();
    int lenb=b.length();
    int i=0,j=0;
    while(i<lena)
    {
        if(a[i]==b[j])
        {
            ++i;++j;
            if(j==lenb)j=Next[j-1]+1;
        }
        else
        {
            if(j==0)i++;
            else
                j=Next[j-1]+1;
        }
    }
}

差不多就是这样

虽然我又又又又又忘了。。。。还是string.find()好