题目链接: Password
大致题意
给定字符串 s s s, 求在串中出现过的最长的匹配的前后缀.
串中出现: 表示出现非前缀且非后缀.
解题思路
kmp
我们考虑对于长度为 n n n字符串 s s s而言, 最长匹配的前后缀一定是 n e x t [ n ] next[n] next[n]. 但该子串并不一定在串中出现.
有可能存在某个短一些的前后缀, 是符合要求的.
首先考虑如何判断最长后缀是否合法
我们不放统计 [ 2 , n ) [2, n) [2,n)区间 n e [ ] ne[] ne[]值的情况, 开一个桶 c o u [ ] cou[] cou[]进行记录.
这样我们只需要判断 c o u [ n e [ n ] ] cou[ne[n]] cou[ne[n]]是否不为 0 0 0即可.
如果最长后缀不合法, 则我们需要考虑次长后缀
我们发现, 次长后缀的长度实质就是 n e [ n e [ n ] ] ne[ne[n]] ne[ne[n]].
若次长后缀不存在, 则无解, 反之, 次长后缀一定是答案.
因为次长后缀一定出现于串中
AC代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
const int N = 1E6 + 10;
char s[N];
int ne[N], cou[N];
int main()
{
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 2, j = 0; i <= n; ++i) {
while (j and s[i] != s[j + 1]) j = ne[j];
if (s[i] == s[j + 1]) ++j;
ne[i] = j;
if (i != n) cou[ne[i]]++;
}
int len = 0;
if (cou[ne[n]]) len = ne[n];
else len = ne[ne[n]];
if (!len) puts("Just a legend");
else s[len + 1] = 0, printf("%s\n", s + 1);
return 0;
}