nowcoder-15165-字符串问题-kmp

题目描述
有一个字符串 让你找到这个字符串 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
**/