Codeforces|Codeforces126B Password (KMP) 算法|c++|Codeforces|kmp|字符串|字

题目链接: 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]].
若次长后缀不存在, 则无解, 反之, 次长后缀一定是答案.

【Codeforces|Codeforces126B Password (KMP)】因为次长后缀一定出现于串中

AC代码

#include #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; }

END