KMP算法

KMP可以在$O(n)$的时间内解决两个字符串匹配问题。

引出KMP

假定两个字符串：
模式串$S$：$ABABABABAA$
模板串$P$：$ABABAA$

我们可以发现在第6个位置发生了失配，依照暴力想法，是移动$p$串到下一个位置。但发现移动之后第一个就不匹配，继续移动。

我们发现第三次在8发生了失配，如果继续按照朴素想法那又得在下一个位置重头从模式串匹配。那我们有没有什么方法能快速使得字符串从图一的失配位置直接跳到图二的位置呢。这时就引入KMP算法。

前缀函数

在引入KMP算法之前，我们观察两幅图的跳转位置，$ABABA$->$ABA$，发现什么了吗，$ABA$是$ABABA$的非平凡前缀（最后一个字符以外，一个字符串的全部头部组合）和非平凡后缀（除了第一个字符以外，一个字符串的全部尾部组合）的最长共有元素的长度。
前缀函数就是满足此定义：$ne[i]$是$s[0..i]$最长的相等的非平凡前后缀的长度。

字符串	前缀集合	后缀	ne
A	空集	空集	0
AB	{A}	{B}	0
ABA	{A，AB}	{A，BA}	1
ABAB	{A，AB，ABA}	{B，AB，BAB}	2
ABABA	{A，AB，ABA，ABAB}	{A，BA，ABA，BABA}	3
ABABAA	{A，AB，ABA，ABAB，ABABA}	{A，AA，BAA，ABAA，BABAA}	1

那我们如何求解$ne$数组呢?
$ne$数组的求法是通过模板串自己与自己进行匹配操作得出来的

当我们求$ne[5]$时，此时已经求的$ne[4]=2$，此时$i=5$，$j=2$，$p[i]=p[j+1]$，当前字符匹配，可以直接通过$ne[4]$转移过来，$ne[5]=ne[4]+1=3$。

接下来求$ne[6]$时，此时$i=6$，$j=3$，$p[i]!=p[j+1]$，当前字符不匹配，那么我们要根据$ne$数组将已经匹配的字串$ABA$移动到其最大前后缀$A$的位置$ne[j]$，此时$j=1$,$p[j+1]=B$也不等于$s[i]$，继续移动$ne[j]$，此时$j=0$，$p[j+1]=s[i]$，$ne[6]=ne[j]+1=1$。

求解$ne$数组代码：

for(int i = 2, j = 0; i <= n; i ++)
        {
            while(j && p[i] != p[j + 1])//失配， 移动p串
                j = ne[j];
            if(p[i] == p[j + 1])//当前元素匹配，j移向p串下一位
                j ++;
            ne[i] = j;//匹配成功，继续匹配下一个子串
        }

匹配代码：

 for(int i = 1,j = 0; i <= m; i ++)
        {
            while(j && s[i] != p[j + 1])
                j = ne[j];
            if(s[i] == p[j + 1])     j ++;
            if(j == n)
                {
                    printf("%d ", i - n);
                    j = ne[j];
                }
        }

Q.E.D.