扩展KMP问题
给定母串S,子串T。定义n = len(S), m = len(T), exend[i] = S[i....n-1]与T的最长公共前缀，在线性时间复杂度内，求出所有的extend[0....n-1].
如果有某个位置i满足extend[i] = m，那么T就肯定在S中出现过，并且进一步知道首位置是i——经典的KMP问题。
由此可见，“扩展的KMP问题”是对经典KMP问题的一个扩充。
求解扩展KMP问题
假设已有针对子串T的next数组，next数组的定义为：
next[i]表示T[i....m-1] 和 T[0...m-1]的最长相同前缀。即next[i] = max{z | T[0...z-1] = T[i, i + z - 1]}
并且已经知道 extend[0]..extend[k-1] 的值，进一步求extend[k]的值。
此时，假设1...k中的a是使得 i + extend[i] - 1( 0 =< i <= k)最大的那个i，且p = a + extend[a] - 1。 
根据定义有 S[a...p] = T[0...p-a], 于是有 S[k...p] = T[k-a...p-a]，令L = next[k-a]，此时有两种情况：
(1) k + L -1 < p 
此时，会出现上图所示情况，图中用T[0...L-1]代替T[k-a, ...k-a+L-1]的部分（即下方的绿色部分），绿色部分一定相同，红色部分一定不同，否则会和next[i]为T[i...m]和T的最长相同前缀长度矛盾。此时，可以看出extend[k] = L.
(2) k + L -1 >= p 
此时，会出现上图所示情况，图中用T[0...L-1]代替T[k-a, ...k-a+L-1]的部分（即下方的红色和紫色部分），绿色部分一定相同，紫色部分不一定相同
。此时需要比较 S[p+1]和T[p-k+1]，S[p+2]和T[p-k+2]....直到失配为止。匹配完之后，比较extend[a] + a和extend[k] + k的大小，如果后者大，则更新a。
算法的时间复杂度
该算法为线性算法，容易看出，在计算的过程中，凡是访问过的点，都不需要重新访问。一旦比较，比较的都是以前从不曾访问过的点，因此总的时间复杂度为O(n+m).
next数组的求解
母串和子串都使用T，则next数组即为extend数组。可以确定next[0] = m，然后按照求extend的方法求解即可。
实现(c++)
void GetNext(char* sub_str, int* next){
int m = strlen(sub_str);
next[0] = m;
next[1] = 0;
for (int i = 0; i < m - 1; i++){
if (sub_str[i] == sub_str[i + 1])
next[1] ++;
else
break;
}
int a = 1; //确定next[0]和next[1]
for (int k = 2; k < m; k++){
int p = next[a] + a - 1;
int L = next[k - a];
if (k + L - 1 < p){
next[k] = L;
}
else{
int j = p + 1 - k > 0 ? p + 1 - k : 0; //注意 p = a + next[a] - 1 可能比较小，比如为0， 此时p+1-k 可能小于0；
//j必须调整为大于等于0
while (j + k < m && sub_str[j + k] == sub_str[j]){
++j;
}
next[k] = j;
a = k;
}
}
}
void GetExtend(char* mas_str, char* sub_str, int* next, int* extend){
int n = strlen(mas_str);
int m = strlen(sub_str);
int i = 0;
extend[0] = 0;
while (mas_str[i] == sub_str[i]){
++i;
extend[0]++;
}
int a = 0; //确定extend[0]
for (int k = 1; k < n; k++){
int p = a + extend[a] - 1;
int L = next[k - a];
if (k + L - 1 < p){
extend[k] = L;
}
else{
int j = p - k + 1 > 0 ? p - k + 1 : 0; ////注意 j必须大于等于0
while (i < n && j < m && mas_str[j+k] == sub_str[j]){
++j;
}
a = k;
extend[k] = j;
}
}
}