传送门
刚开始练KMP题目,自己好菜啊...
这道题思路大致上对了,但是细节上出现了很大的偏差。
问题在于对于回文串的情况没有想全,仅仅想到了非重复回文串如abcdeabc以及单一回文串aaaaaa,于是考虑了两种情况,但是还有一种就是重复非单一回文串,用我的思路直接是求出next数组,分情况讨论,对于非单一的肯定就一种情况,但是如果出现abcabcabc那么 next[n] 就会是6,而目标是用3来求,不仅如此还打算用扩展kmp,Z算法来求,于是这样就错了。
看了题解才发现自己完全想多了,只需要在遍历中判断next[i]是否等于next[n]就可以了,这样就能保证是满足题意的,同时在求next数组中求出除了最后一位的next最大值,设其为maxn,有可能maxn是小于n的,那么这样就不满足条件如aaaaa,next[4] = 3 != next[5],所以要将长度缩小,也就是将首尾相同的串的长度缩小,直到小于等于这个中间最长串。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char s[N];
int ne[N], ne1[N], extend[N];
int maxn = 0;
int main(){
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;
if(i != n)
maxn = max(maxn, ne[i]);
}
if(ne[n] == 0){
cout << "Just a legend" << endl;
return 0;
}
int x = ne[n];
while(maxn < x)
x = ne[x];
if(x == 0){
cout << "Just a legend" << endl;
return 0;
}
for(int i = 2; i <= n - 1; i ++){
if(ne[i] == x){
for(int j = n - ne[i] + 1; j <= n; j ++){
printf("%c", s[j]);
}
return 0;
}
}
//以下为废弃代码
/*string str, p;
p += "@";
for(int i = 2; i <= n - 1; i ++)
p += s[i];
cout << ne[n] << endl;
if(ne[n] > 0 && s[1] != s[n]){
for(int i = n - ne[n] + 1; i <= n; i ++)
str += s[i];
str = "@" + str;
int len = ne[n];
for(int i = 2, j = 0; i <= n - 2; i ++){
while(j && p[i] != p[j + 1])
j = ne1[j];
if(p[i] == p[j + 1])
j ++;
ne1[i] = j;
}
for(int i = 2, j = 0; i <= n - 2; i ++){
while(p[i] != str[j + 1] && j)
j = ne1[j];
if(p[i] == str[j + 1])
j ++;
if(j == len){
for(int i = n - ne[n] + 1; i <= n; i ++)
printf("%c", s[i]);
return 0;
}
}
printf("Just a legend\n");
}else if(ne[n] > 0 && s[1] == s[n]){
for(int i = n - ne[n] + 1; i <= n; i ++)
str += s[i];
int len = ne[n];
getExtend(p, str);
int maxn = -1;
for(int i = 1; i <= n - 2; i ++)
maxn = max(maxn, extend[i]);
for(int i = 1; i <= n; i ++)
cout << extend[i] << ' ';
cout << endl;
for(int i = n - maxn + 1; i <= n; i ++)
printf("%c", s[i]);
}
*/
return 0;
}