大名鼎鼎的KMP算法，是一种在线性时间内能处理两个字符串的包含关系的算法，少废话，我们开始。
引入
给定两个字符串O和f，长度分别为n和m，
判断f是否在O中出现，如果出现则返回出现的位置。
常规方法是遍历O的每一个字符的位置，找到某一个字符刚好和f[0]相同，后，再从该位置开始和f进行匹配，但是这种方法的复杂度是O(nm)。
kmp算法通过一个O(m)的预处理，使匹配的复杂度降为O(n+m)
思想
我们首先用一个图来描述kmp算法的思想。
在字符串O中寻找f，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。
常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过了，所以效率不高。
事实上，如果我们提前计算某些信息，就有可能一次前移不止一位。
假设我们根据已经获得的信息知道可以前移k位，我们分析移位前后的f有什么特点。看上图，我们可以得到如下的结论：
- A段字符串是f的一个前缀。
- B段字符串是f的一个后缀。
- A段字符串和B段字符串相等。
这就意味着，我们的算法最重要的是，计算字符串f每一个字符位置之前的字符串的前缀和后缀公共部分的最大长度（不包括字符串本身，否则最大长度始终是字符串本身）。
获得f每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串O比较。
分析
当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最大公共长度)位，接着继续比较下一个位置。事实上，字符串f的前移只是概念上的前移，只要我们在比较的时候从最大公共长度之后比较f和O即可达到字符串f前移的目的。
看到这个图，自然就会想到，我们得计算next数组，怎么算呢？看着上图继续往下分析：
首先，next数组表示的是长度，下标从1开始；因为在遍历原字符串时，下标还是从0开始。假设我们现在已经求得next[1]、next[2]、……next[i]，分别表示长度为1到i的字符串的前缀和后缀最大公共长度，现在要求next[i+1]。
由上图我们可以看到，
如果位置i和位置next[i]处的两个字符相同（下标从零开始），则next[i+1]等于next[i]加1。
如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继续分割，获得其最大公共长度next[next[i]]，然后再和位置i的字符比较。
为什么呢？这是因为长度为next[i]前缀和后缀都可以分割成上图所示的构造，
如果位置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。
如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符串长度为0为止。
看懂上面的图异常重要
模板
求一个字符串里有没有另一个字符串，一个字符串里有几个另一个字符串（可重叠和不可重叠两种）。
可重叠
#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])
{
int q,k;
int m = strlen(P);
next[0] = 0;
for (q = 1,k = 0; q < m; ++q)
{
while(k > 0 && P[q] != P[k])
k = next[k-1];
if (P[q] == P[k])
{
k++;
}
next[q] = k;
}
}
int kmp(const char T[],const char P[],int next[])
{
int n,m;
int i,q;
n = strlen(T);
m = strlen(P);
makeNext(P,next);
for (i = 0,q = 0; i < n; ++i)
{
while(q > 0 && P[q] != T[i])
q = next[q-1];
if (P[q] == T[i])
{
q++;
}
if (q == m)
{
printf("Pattern occurs with shift:%d\n",(i-m+1));
}
}
}
int main()
{
int i;
int next[20]={0};
char T[] = "ababxbababcadfdsss";
char P[] = "abcdabd";
printf("%s\n",T);
printf("%s\n",P );
// makeNext(P,next);
kmp(T,P,next);
for (i = 0; i < strlen(P); ++i)
{
printf("%d ",next[i]);
}
printf("\n");
return 0;
}
不可重叠
#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])
{
int q,k;
int m = strlen(P);
next[0] = 0;
for (q = 1,k = 0; q < m; ++q)
{
while(k > 0 && P[q] != P[k])
k = next[k-1];
if (P[q] == P[k])
{
k++;
}
next[q] = k;
}
}
int kmp(const char T[],const char P[],int next[])
{
int n,m;
int i,q;
n = strlen(T);
m = strlen(P);
makeNext(P,next);
for (i = 0,q = 0; i < n; ++i)
{
while(q > 0 && P[q] != T[i])
q = next[q-1];
if (P[q] == T[i])
{
q++;
}
if (q == m)
{
printf("Pattern occurs with shift:%d\n",(i-m+1));
q = 0;
}
}
}
int main()
{
int i;
int next[20]={0};
char T[] = "ababababa";
char P[] = "aba";
printf("%s\n",T);
printf("%s\n",P );
// makeNext(P,next);
kmp(T,P,next);
for (i = 0; i < strlen(P); ++i)
{
printf("%d ",next[i]);
}
printf("\n");
return 0;
}
