重新看了KMP算法，有了新的理解。主要参考资料
/Files/bon/kmp2.pdf附件里说得很好，跟传统的教程不同。
首先定义串s的前缀s'，空串也是s的前缀，还有一个定义叫做proper prefix：s'是s的proper prefix等价于s'是s的prefix且s' != s，这个定义对于理解KMP有着关键的作用。同样可以定义对应的后缀以及proper suffix。
下面假设模式串为s，被匹配的串为t，且第0个字符是串的第一个字符。
KMP的精髓在于计算next数组（附件里为pi数组）。next[i]=k，k<i（注意这里不取等号，想想为什么），s[0...k]是s的proper prefix，也是s[0...i]的proper suffix，且k是最大的（即不存在l>k，s[0...l]是s[0...i]的proper prefix且是s[0...i]的proper suffix）。
那么next[0]=-1就很自然地被理解：表示的是空串是s[0...0]的proper prefix且是s[0...0]的proper suffix。
另外k严格小于i也可以理解：若k==i，但s[0...i]不是s[0...i]的proper prefix 也不是proper suffix，这跟定义冲突。
上述可以用下图来说明。
上面的式子定义了next数组，但还没有指出怎么计算next。假设next[0...i]已经计算出来了，next[i+1]怎么算。
这里用的是动态规划的思想。设s[0...k+1]是s[0...i+1]最长的proper prefix且是proper suffix，k<i，则明显地s[0...k+1]符合以下性质：
1. s[0...k]是s[0...i]的proper prefix (这一点很明显，由于k<i)
2. 且s[0...k]是s[0...i]的proper suffix (若不然，s[0...k+1]肯定无法组成s[0...i+1]的suffix)
3. 且s[k+1]==s[i+1]。
因此我们的任务就是找到这样一个k。而s[0...k]是s[0...i]的proper prefix 和proper suffix这个性质使得我们可以利用已计算的next[0...i]来找k。
找的过程实质就是找到s[0...i+1]一个最长的proper prefix s[0...k], 这个prefix 同时是s[0...i+1]的proper suffix且有s[i+1]==s[k+1]，见下图：
假设s[0...kx]都是s[0...i+1]的proper prefix，且都是s[0...i]的proper suffix。设s[k
1+1] != s[i+1]，则s[0...k
1+1]不可能是s[0...i+1]的proper suffix。
设s[k
2+1] = = s[k
3+1] = = s[i+1]，但由于k
3>k
2，所以next[i+1] = k
3+1
下面看poj上的一道
题目的代码：
1 #include <iostream>
2
3 using namespace std;
4
5 char w[10001],t[1000001];
6 int n;
7 int next[10001];
8
9 int main()
10 {
11 scanf("%d",&n);
12 while(n--){
13 scanf("%s",w);
14 scanf("%s",t);
15 // process w
16 int wLength = strlen(w);
17 next[0]=-1;
18 int i=1;
19 int p;
20 while(i<wLength){
21 p=next[i-1];
22 while(p!=-1 && w[p+1]!=w[i]) p=next[p];
23 if(w[p+1]==w[i]) next[i]=p+1;
24 else next[i]=-1;
25 i++;
26 }
27 //for(i=0;i<wLength;i++) printf("%d",next[i]);
28 //printf("\n");
29 // matching
30 int j=-1,cnt=0;
31 i=-1;
32 int tLength = strlen(t);
33 while(j<tLength){
34 if(t[j+1]==w[i+1]){
35 i++;
36 j++;
37 if(i==wLength-1){
38 cnt++;
39 i=next[i];
40 }
41 }else{
42 if(i==-1) j++;
43 else i=next[i];
44 }
45 }
46 printf("%d\n",cnt);
47 }
48 return 1;
49 }
50