题目描述
给定一个字符串s
,求最大的前缀等于后缀等于中间缀
样例
//输入
2
fixprefixsuffix
abcdabc
//输出
fix
not exist
算法1
(KMP) $O(n)$
对于字符串s
,我们可以处理处ne
数组,ne[i]
表示字符串s[1-i]
最大的后缀等于前缀的长度
st[i]
表示ne[2~n-1]中有=i
的情况
先判断最大的后缀等于前缀p = ne[n]
是否存在,即st[p]
,存在即说明2~n-1
存在。
否则p = ne[p]
,这里保证了前缀=后缀=中缀,就是没想到这里导致一直过不去ORZ。
时间复杂度
KMP时间复杂度$O(n)$,然后依次枚举q
,$O(n)$,总的时间复杂度$O(n)$.
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
char s[N], st[N];
int T, ne[N];
int main()
{
scanf("%d", &T);
while (T --) {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 2, j = 0; i <= n; i ++) {
while (j && s[i] != s[j + 1]) j = ne[j];
if (s[i] == s[j + 1]) j ++;
ne[i] = j;
}
memset(st, 0, sizeof st);
for (int i = 2; i < n; i ++)
if (ne[i]) st[ne[i]] = 1;
int ans = -1;
int p = ne[n];
while (p) {
if (st[p]) ans = max(ans, p);
p = ne[p];
}
// cout << n <<" " <<ans << endl;
if (ans == -1) printf("not exist\n");
else {
for (int i = 1; i <= ans; i ++) printf("%c", s[i]);
printf("\n");
}
}
}