描述
题解
求既是前缀串儿又是后缀串儿的不同子串的长度,长度从小到大输出。
这里很容易想到要用 next[] ,这个数组也就是 prefix 数组,代表匹配失配时前跳的情况,并且保证前缀都是相同的,只需要继续从失配处前跳的位置开始检查即可,那么如果我们从字符串尾部开始不断回溯前跳,当新的匹配位置和最后一个字符相同时,说明此时的前缀串是可以和对应长度的后缀串儿进行匹配的,则将答案存储下来,最后逆序输出即可,注意最后还要加上长度为模式串长度的结果,因为每个串其本身也是满足既等于前缀也等于后缀的,也就是题中所说的 prefix-suffix string of S 。
代码
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 1e6;
int n;
char s[MAXN];
int nxt[MAXN];
vector<int> ans;
void getnxt()
{
nxt[0] = -1;
int i = 0, j = -1;
int len = (int)strlen(s);
while (i < len)
{
if (j == -1 || s[i] == s[j])
{
i++;
j++;
nxt[i] = j;
}
else
{
j = nxt[j];
}
}
}
int main()
{
while (~scanf("%s", s))
{
int len = (int)strlen(s);
getnxt();
ans.clear();
int pos = nxt[len - 1];
while (pos != -1)
{
if (s[pos] == s[len - 1])
{
ans.push_back(pos + 1);
}
pos = nxt[pos];
}
for (int i = (int)ans.size() - 1; i >= 0; i--)
{
printf("%d ", ans[i]);
}
printf("%d\n", len);
}
return 0;
}