题意：
就是求前缀和后缀相同的那个子串的长度 然后从小到大输出
解析：
emm。。。网上都用kmp。。。我。。用拓展kmp做的 这就是拓展kmp板题嘛。。。
求出extend数组后 把extend[i] == len - i 的放到vector中 最后排序输出就好了
当然可以用kmp。。emm。。还是没有透彻kmp的next数组和 拓展kmp的next数组的意义
这段写给自己看：
kmp的next是前缀和后缀的完全匹配（k - （i-1））的最长长度
拓展kmp的next是前缀和后缀（i - len）的最长匹配
这两个后缀的意义还不同。。。。emm。。
kmp的 abcdefg 当i == 3时 后缀为 d cd bcd
拓展kmp的 abcdefg 当i == 3 时 后缀为 defg
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 400010, INF = 0x7fffffff; 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<len)//计算next[1] i++; next[1]=i; po=1;//初始化po的位置 for(i=2;i<len;i++) { if(next[i-po]+i<next[po]+po)//第一种情况，可以直接得到next[i]的值 next[i]=next[i-po]; else//第二种情况，要继续匹配才能得到next[i]的值 { j=next[po]+po-i; if(j<0)j=0;//如果i>po+next[po],则要从头开始匹配 while(i+j<len&&str[j]==str[j+i])//计算next[i] j++; next[i]=j; po=i;//更新po的位置 } } } //计算extend数组 void EXKMP(char *s1,char *s2) { int i=0,j,po,len=strlen(s1),l2=strlen(s2); GETNEXT(s2);//计算子串的next数组 while(s1[i]==s2[i]&&i<l2&&i<len)//计算ex[0] i++; ex[0]=i; po=0;//初始化po的位置 for(i=1;i<len;i++) { if(next[i-po]+i<ex[po]+po)//第一种情况，直接可以得到ex[i]的值 ex[i]=next[i-po]; else//第二种情况，要继续匹配才能得到ex[i]的值 { j=ex[po]+po-i; if(j<0)j=0;//如果i>ex[po]+po则要从头开始匹配 while(i+j<len&&j<l2&&s1[j+i]==s2[j])//计算ex[i] j++; ex[i]=j; po=i;//更新po的位置 } } } char s1[maxn]; int main() { while(~scanf("%s", s1)) { vector<int> v; EXKMP(s1, s1); int len = strlen(s1); for(int i=0; i<len; i++) if(ex[i] == len-i) v.push_back(ex[i]); sort(v.begin(), v.end()); for(int i=0; i<v.size(); i++) { if(i != 0) printf(" "); printf("%d", v[i]); } printf(" "); } return 0; }
kmp做法
设s的长度为n，则s串本身必定满足条件。其他满足条件的子串都有个特征，就是该子串的最后一个字符肯定与s的最后一个字符相同。这正是next数组发挥作用的时候。从n - 1位既最后一位开始回滚，若s[next[n-1]] == s[n-1]，则子串s[0,1,2,...,next[n-1]]是满足条件的子串。然后判断s[next[next[n-1]]] == s[n-1]是否成立，这样一直回滚，直到next[next[.....next[n-1]]] == -1为止。把答案从大到小存下来，再从小到大输出即可