题目
思路
- 看到前后缀就想到kmp了
- 要求的是字符串的所有前后缀相同的长度
- KMP的next求解的时候，如果P[k]!=P[j]，就令k=NEXT[k]，这样找到的k之前的字符串仍然是与后缀相等的前缀（但是变短了）。
- 最后得到的next数组，next[k]储存的是满足条件的最长前缀的长度，那么满足条件的前缀只需要遍历k = next[k]，直到长度为0就行了。
AC代码
#include<iostream>
#include<stack>
using namespace std;
const int MAXN=10000002;
string P;
string T;
int NEXT[MAXN];
int plen,tlen;
void getNEXT(){
NEXT[0] = -1;
int k = -1 ;
int j = 0 ;
while(j<plen){
if(k==-1||P[k]==P[j]){
NEXT[++j] = ++k;
}else{
k = NEXT[k];
}
}
}
int main(){
ios::sync_with_stdio(false);
while(cin>>P){
plen=P.length();
getNEXT();
// for(int i = 0 ; i<=plen;i++){
// cout<<" "<<NEXT[i];
// }
stack<int> S;
int k = plen;
S.push(plen);
while(NEXT[k] != 0){
k = NEXT[k];
S.push(k);
// cout<<"k"<<k<<"\n";
}
int size = S.size();
while(size--){
if(size!=0)
cout<<S.top()<<" ";
else cout<<S.top();
S.pop();
}
cout<<"\n";
// P="";
}
return 0;
}
