题目来源:http://poj.org/problem?id=2752
题目描述:
题意:
给定一个字符串s,求有哪些长度的s的前缀,同时也是s的后缀。
思路:
对于字符串s的第i个字符s[i]
,next[i]
定义为字符s[i]
前面最多有多少个连续的字符和字符串s从初始位置开始的字符匹配。那么我们可以从后到前匹配前缀和后缀,如果前缀与后缀匹配,则下一个前缀与后缀匹配的字符串必然在前缀中。不断递归next数组即可求解。
参考代码:
#include <iostream>
using namespace std;
const int N=4e5+10;
#define end '\n'
#define IOS ios::sync_with_stdio(0)
int nxt[N],len,ans[N];
string s;
void get_next(string p) {
len = p.size();
int j = 0, k = -1;
nxt[0] = -1;
while (j < len) {
if (k == -1 || p[j] == p[k]) {
nxt[++j] = ++k;
} else {
k = nxt[k];
}
}
}
int main() {
IOS;
while (cin >> s) {
get_next(s);
/*从字符串的尾部开始,下一个前后缀匹配的串只能在与后缀相同的前缀字符串中*/
int sum = 0;
int t = nxt[len - 1];
while (t != -1) {
if (s[t] == s[len - 1])
ans[sum++] = t + 1;
t = nxt[t];
}
for (int i = sum - 1; i >= 0; i--) {
cout << ans[i] << " ";
}
cout << len << end;
}
return 0;
}