扩展KMP

给定串S和T，求S的每一个后缀和T的最长公共前缀。

方法1：暴力算法，时间复杂度O(n^2);

方法2:后缀数组，利用height的性质可以求出该问题，时间复杂度为O(n),但是预处理为O(nlogn)

方法3:扩展KMP，充分利用已经匹配过的性质，降低匹配的时间,时间复杂度为O(n)

学习资料：http://www.docin.com/p-423302546.html

设next[i]为这样一个数组，next[i]为串T的suffix(i)和suffix(0)的相似度，假设next[0-->k-1]已经算出了，并且在以前的匹配中，

匹配到的最远处为p，如图

假设是suffix(a)和suffix(0)匹配到最远处p，那么有T[a-->p] == T[0-->p-a+1]那么这个匹配的后面一段也相等，即T[k-->p]==T[k-a-->p-a+1],

又因为next[k-a]是已知的,令L = next[k-a]

有两种情况，

①k+L-1 < p，那么next[k] = L,不可能大于L，否则next[k-a] 就不等于L了，可能有人会想到，为什么表示k+L-1<=p，这个因为，如果取等号，那么p+1的部分没被判断过，所以不能直接next[k] = L;

②K+L-1>=p, 那么要重新匹配超过p的部分，即T[p+1] 和T[p-k+1]重新匹配。

九度oj 1535

 1 /*next[i] 表示T[i-->n]和T[0-->n]的相似度
 2 */
 3 
 4 #include <stdio.h>
 5 #include <string.h>
 6 const int N = 1000000 + 10;
 7 char S[N],T[N];
 8 int next[N];
 9 int extend[N];
10 void makeNext()
11 {
12     int n,a,j,k,L,p;
13     next[0] = n = strlen(T);
14     a = 0;
15     while(a+1<n && T[a]==T[a+1]) a++;
16     next[1] = a;
17     a = 1;
18     for(k=2; k<n; ++k)
19     {
20         p = a + next[a] - 1;
21         L = next[k-a];
22         if(k+L-1>=p)
23         {
24             //这一切都要求p>=k,否则，从新从0开始匹配。
25             j = p - k + 1 > 0 ? p-k+1 : 0;
26             while(k+j<n && T[k+j]==T[j]) ++j;
27             next[k] = j;
28             a = k;
29         }
30         else
31             next[k] = L;
32 
33     }
34 
35 }
36 void makeExtend()
37 {
38     int sLen = strlen(S),tLen = strlen(T);
39     int len = sLen < tLen ? sLen : tLen;
40     int a = 0,k,j,L,p;
41     while(a<len && S[a]==T[a]) a++;
42     extend[0] = a;
43     a = 0;
44     for(k=1; k<sLen; ++k)
45     {
46         p = a + extend[a] -1;
47         L = next[k-a];
48         if(k+L-1>=p)
49         {
50             j = p-k+1>0?p-k+1:0;
51             while(k+j<sLen&&j<tLen &&S[k+j]==T[j])
52                 j++;
53             extend[k] = j;
54             a = k;
55         }
56         else
57             extend[k] = L;
58     }
59 }
60 int main()
61 {
62     while(scanf("%s%s",S,T)!=EOF)
63     {
64         makeNext();
65         makeExtend();
66         int n = strlen(S);
67         int ans = 0;
68         for(int i=0; i<n; ++i)
69             if(extend[i] == n - i)
70             {
71                 ans = extend[i];
72                 break;
73             }
74         printf("%d
",ans);
75     }
76     return 0;
77 }