给定两个字符串S和T（长度分别为n和m），下标从0开始，定义extend[i]等于S[i]...S[n-1]与T的最长公共前缀的长度，求出所有的extend[i]
next[i]： T[i]...T[m-1]与T的最长公共前缀长度；
extend[i]： S[i]...S[n-1]与T的最长公共前缀的长度。
推荐博客：https://wenku.baidu.com/view/8e9ebefb0242a8956bece4b3.html
1 //C/C++ 模板 2 #include <iostream> 3 #include <stdio.h> 4 #include <string.h> 5 using namespace std; 6 const int N = 101010; 7 int next[N],extand[N]; 8 void getnext(char *T){// next[i]: 以第i位置开始的子串 与 T的公共前缀 9 int i,length = strlen(T); 10 next[0] = length; 11 for(i = 0;i<length-1 && T[i]==T[i+1]; i++); //单独处理next[1] 12 next[1] = i; 13 int a = 1; 14 for(int k = 2; k < length; k++){ 15 int p = a+next[a]-1, L = next[k-a]; 16 if( (k-1)+L >= p ){ 17 int j = (p-k+1)>0? (p-k+1) : 0; 18 while(k+j<length && T[k+j]==T[j]) j++;// 枚举(p+1，length) 与(p-k+1,length) 区间比较 19 next[k] = j, a = k; 20 } 21 else next[k] = L; 22 } 23 } 24 void getextand(char *S,char *T){ 25 memset(next,0,sizeof(next)); 26 getnext(T); 27 int Slen = strlen(S), Tlen = strlen(T), a = 0; 28 int MinLen = Slen>Tlen?Tlen:Slen; 29 while(a<MinLen && S[a]==T[a]) a++; 30 extand[0] = a, a = 0; 31 for(int k = 1; k < Slen; k++){ 32 int p = a+extand[a]-1, L = next[k-a]; 33 if( (k-1)+L >= p ){ 34 int j = (p-k+1)>0? (p-k+1) : 0; 35 while(k+j<Slen && j<Tlen && S[k+j]==T[j] ) j++; 36 extand[k] = j;a = k; 37 } 38 else extand[k] = L; 39 } 40 } 41 42 int main(){ 43 char s[N],t[N]; 44 while(~scanf("%s %s",s,t)){ 45 getextand(s,t); 46 for(int i = 0; i < strlen(t); i++) printf("%d ",next[i]); 47 puts(""); 48 for(int i = 0; i < strlen(s); i++) printf("%d ",extand[i]); 49 puts(""); 50 } 51 } 52 53 /* 54 abababab abab 55 aaaabaaa aaaa 56 */
只有不断学习才能进步！