前后缀的重合,很有KMP的感觉
next(或者pre)的妙用
最后输出答案用了递归
#include <string>
#include <iostream>
#define MAXN 400005
using namespace std;
string str;
int pre[MAXN];
int T;
void dfs(int size) {
if(size==0) return;
dfs(pre[size]);
printf("%d ",size);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
while( cin >> str ) {
int size = str.length(); str = ‘ ‘ + str;
pre[1] = 0; int len = 0;
for(int i=1;i<size;++i) {
while(len&&str[i+1]!=str[len+1]) len = pre[len];
if(str[i+1]==str[len+1]) len++;
pre[i+1] = len;
}
dfs(size); puts("");
}
}