题目描述
有一个 字符串 让你找到这个字符串 S 里面的子串T 这个子串 T 必须满足即使这个串的前缀 也是这个
串的后缀 并且 在字符串中也出现过一次的(提示 要求满足前后缀的同时也要在字符串中出现一次 只是前后缀可不行 输出最长满足要求字符串)
输入描述:
给出一个字符串 长度 1 到 1e6 全部是小写字母
输出描述:
如果找的到就输出这个子串T 如果不行就输出 Just a legend
示例1
输入
fixprefixsuffix
输出
fix
示例2
输入
abcdabc
输出
Just a legend
题意非常简单明了，求出最长的子串，使得这个子串即是前缀也是后缀，并且在字符串中出现过
有一个比较重要的一点可能不容易被考虑到，比如有一个字符串是：
abababa
那么对于这个字符串来讲的最长的子串就是aba，貌似是可以有重叠的部分
通过题意，很容易想到不考虑中间出现过该字串的情况，我们可以考虑使用 KMP，KMP中有一个重要的性质就是最长公共的前后缀。因此在不考虑中间存在的情况时，我们就可以输出该字符串 前next[len]个字符
如果说next[len] == -1 那么说就不存在这个子串
那么考虑上中间出现过该字符串的情况：
我们记录下最后一个点的next值，看这个值出现过是不是 > 0次，如果说 > 0次，就输出前面的[0 , next[len] ] 即可
反之再看next[next[len]] 是否 > 0， > 0就输出 [0 , next[next[len] ]反之输出 Just a legend
const int mod = 1000000007; #define PI acos(-1.0) typedef int itn; int nex[1000007]; string s; int len; void getNex(){ int i=0,j=-1; nex[0] = -1; while(i < len){ if(j == -1 || s[i] == s[j]) nex[++i] = ++j; else j = nex[j]; } } int cnt[maxn]; int main() { cin >> s; len = s.size(); getNex(); for(int i=1;i<len;i++) cnt[nex[i]] += 1; /// for(int i=0;i<=len;i++) cout<<i<<' '<<nex[i] << endl; int t = nex[len]; /// cout<< t << endl; if(t <= 0) puts("Just a legend"); else{ if(cnt[t]) cout<<s.substr(0,t)<<endl; else if(nex[t]) cout<<s.substr(0,nex[t]) <<endl; else puts("Just a legend"); } return 0; } /** abababa aba **/
