举个例子
模式串S：a s d a s d a s d f a s d
匹配串T：a s d a s d f
如果使用朴素匹配算法——
1 2 3 4 5 6 8 9
a s d a s d a s d f a s d
a s d a s d f
1 2 3 4 5 6
此时，匹配到了S7和T7了，S7为a而T7为f，不匹配那么朴素的匹配算法会这么做——
1 3 4 5 6 7 8 9
a s d a s d a s d f a s d
a s d a s d f
1 2 3 4 5 6 7
这时，我们会发现，模式串回溯到了S2，而匹配串回溯到了T1。
很明显，这会极大的降低算法的效率，在最坏情况下，我们需要将模式串几乎每个元素都查询一次，而每次查询都从匹配串的串首走到接近串尾，这样的时间复杂度为n*m，其中n和m分别为模式串和匹配串的长度。
那么我们是否有可能降低时间复杂度呢？答案是肯定的——很明显我们只需要想办法减少回溯，就可以达到效果。Kmp算法就是使用这种方法节省时间的。
1 2 3 4 5 6 8 9
a s d a s d a s d f a s d
a s d a s d f
1 2 3 4 5 6 7
这个东西很熟悉吧？刚刚出现过一次。
那么，kmp算法会怎么执行下一步呢？答案如下——
1 2 3 4 5 6 8 9
a s d a s d a s d f a s d
a s d a s d f
1 2 3 5 6 7
注意这一步！这里的模式串根本没有回溯，只是将匹配串向后移动了若干步。这样，最坏情况只是将模式串走一遍，然后将匹配串走一遍，当然了，匹配串里面的部分元素会走多次，但是，很明显这种算法会将n*m降低到n+k，这个k和m内部部分元素的重复次数有关，最大不会超过n（当然这是我自己证明得到的，不一定正确，以后我还会继续证明的）。
好了，方法知道了，那么怎么实现呢？
换句话说，怎么实现迅速的移动匹配串呢？答案是——添加一个Next数组，标记匹配串中的特性。
这个Next数组的特性很明显
- Next[0] = -1，即这是第一个元素，前面没有可以替换它的。
- Next[j] = k ; { k | T[0] = T[j-k], T[1] = T[j-k+1],... , T[k-1] = T[j-1]}。
- Next[j] = 0; 其他情况。
举例：
匹配串T: a s d a s d f
Next: -1 0 0 0 1 2 3
具体见代码——
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; const int N = ; char s[N], t[N];
int Next[N];
int lenS, lenT; void kmpNext(char* T) //计算Next数组
{
int i = ;
Next[] = -; //Next[0] = -1
while(i < lenT)
{
int j = ;
while(T[j] == T[i]) //Next[i] = j; { j | T[0] = T[i-j], T[1] = T[i-j+1],... , T[j-1] = T[i-1]}
{
Next[i] = j;
i++;
j++;
}
Next[i] = j; //同上，或等于0
i++;
}
} bool kmp(char* S, char* T) //kmp
{
lenS = strlen(S);
lenT = strlen(T);
kmpNext(T);
int i = , j = ;
while(i < lenS && j < lenT) //当模式串或匹配串走完时退出
{
if(j == -)
{
i++;
j = ;
}
else if(S[i] == T[j])
{
i++;
j++;
}
else j = Next[j];
}
if(j == lenT) return ; //如果匹配串走完，表示匹配串是模式串的子串
return ;
} int main()
{
//freopen("test.in", "r", stdin);
while(~scanf("%s%s", s, t))
{
if(kmp(s, t)) printf("Yes\n");
else printf("No\n");
}
return ;
}