https://wenku.baidu.com/view/206c8178d0d233d4b04e69ed.html
问题定义：给定两个字符串S和T（长度分别为n和m），下标从0开始，定义extend[i]等于S[i]...S[n-1]与T的最长公共前缀的长度，求出所有的extend[i]。举个例子，看下表：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
|---|---|---|---|---|---|---|---|---|---|
| S | a | a | a | a | a | b | b | b | |
| extend[i] | 5 | 4 | 3 | 2 | 1 | 0 | 0 | 0 | |
| T | a | a | a | a | a | c | |||
为什么说这是KMP算法的扩展呢？显然，如果在S的某个位置i有extend[i]等于m，则可知在S中找到了匹配串T，并且匹配的首位置是i。而且，扩展KMP算法可以找到S中所有T的匹配。接下来具体介绍下这个算法。
计算extend[1]= 10 时，我们得到S[1...10] = T[1...10] S[2...10] = T[2...10]
那么计算extend[2]时 是从S[2]开始 匹配的开头阶段是 以T[2...10]为母串，T为子串的匹配
辅助数组next[i]表示T[i...m]与T的最长公共前缀长度
对上面的例子 next[2]= 10 =》 T[2...11] = T[1...10] => T[2...10] = T[1...9]
所以计算extend[2]时 我们可以直接从S[11] -- T[10]开始比较 发现失配 所以extend[2] = 9
算法：O(n+m)
计算next数组 以T为母串，T为子串的一个特殊的扩展KMP
应用：
求最长公共前缀长度
求字符串中重复子串的长度 i+next[i]
abababccc中ababab就是重复子串，ababa也是重复子串【端点处循环节不完整的也算】
比如ababab next[2] = 4 2,3匹配0,1 4,5匹配2,3相当于还是匹配0,1 只要能匹配上的就是在重复前i个字符 能匹配多长就重复了多长 总长就是i+next[i]
代码模板
void GetExtend(const EleType str[], int strLen, int extend[], const EleType mode[], int modeLen, int next[]){ int i, a, p, j(-1); for(i = 0; i < strLen; ++i,--j){ if(j < 0 || i + next[i - a] >= p){ if(j < 0) j = 0, p = i; while(p < strLen && j < modeLen && str[p] == mode[j]) ++p,++j; extend[i] = j, a = i; } else extend[i] = next[i - a]; }} const int maxn=100010; //字符串长度最大值 int next[maxn],ex[maxn]; //ex数组即为extend数组 //预处理计算next数组 void GETNEXT(char *str) { int i=0,j,po,len=strlen(str); next[0]=len;//初始化next[0] while(str[i]==str[i+1]&&i+1 po+next[po],则要从头开始匹配 while(i+j ex[po]+po则要从头开始匹配 while(i+j