思路
主要考察对next数组的理解
代码
#include <cstdio>
#include <cstring>
#include <stack>
#define maxn 400005
int next[maxn];
char s[maxn];
int N;
std::stack<int>ans;
void get_next() {
int k = 0;
next[0] = 0;
N = strlen(s);
for (int i = 1;i < N;i++) {
while (k > 0 && s[k] != s[i])k = next[k - 1];
if (s[k] == s[i])k++;
next[i] = k;
}
}
int main() {
while (~scanf("%s", s)) {
memset(next, 0, sizeof(next));
get_next();
int t = N - 1;
while (next[t] != 0) {
ans.push(next[t]);
t = next[t] - 1;
}
while (!ans.empty()) {
printf("%d ", ans.top());
ans.pop();
}
printf("%d\n", N);
}
return 0;
}