功能
字符串T，长度为n。
模板串P，长度为m。在字符串T中找到匹配点i，使得从i开始T[i]=P[0], T[i+1]=P[1], . . . , T[i+m-1]=P[m-1]
KMP算法先用O(m)的复杂度对模板串进行处理，然后O(n)进行匹配。总时间复杂度O(m+n)
注意失配函数f[i]为第i位处不能匹配时应当转向检查第f[i]位是否匹配：
比如模板串：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
A |
B |
B |
A |
A |
B |
A |
得到的失配函数为：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
0 |
0 |
0 |
0 |
1 |
1 |
2 |
1 |
也即是说如果在模板串第5位失配，即当前位匹配不成功：
|
字符串 |
X |
X |
A |
B |
B |
A |
A |
K |
X |
|
模板串 |
A |
B |
B |
A |
A |
失配 |
那么根据失配函数f[5]=1，转移到1，表示已经匹配好一位，相当于模板串整体右移，但当前匹配的位置不变，然后继续匹配。
|
字符串 |
X |
X |
A |
B |
B |
A |
A |
K |
X |
|
模板串 |
A |
… |
失配函数另一种用途：如果P存在循环节，f[i]为前一个循环节对应字符的位置。比如ABCABC，那么P[4]=B，而f[5]=2，也就是P[1]=B。
用途：计算字符串循环节长度。
构造失配函数：
s为模板串，f为待构造的失配数组，开始时为空
void getFail(char *s,int *f)
{
int m=strlen(s),j;
f[]=;f[]=;
for (int i=;i<m;i++)
{
j=f[i];
while (j&&s[i]!=s[j]) j=f[j];
f[i+]=(s[i]==s[j]?j+:);
}
}
匹配函数：
输入
t:文本，一大串字符串
s:模板，待匹配的模板
f:失配数组，一开始为空，函数过程中调用失配数组构造函数
输出
t字符串中模板第一次出现的位置（从0开始）
int find(char *t,char *s,int *f)
{
int n=strlen(t),m=strlen(s);
getFail(s,f);
int j=;
for (int i=;i<n;i++)
{
while (j&&s[j]!=t[i]) j=f[j];
if (s[j]==t[i]) j++;
if (j==m) return i-m+;
}
}