题解 | #字符串的问题#

题解思路：
参考楼下大佬的思路：是否有和最后一个next[]相同的next值在数组中间出现，若存在最后一个next就是答案。
否则，next[最后一个next]才是解（当然，特判解不存在）。

这里重点贴一下代码，其中未注释代码为从 0 开始的 next 数组求解，注释的代码则是从 1 开始的 next 数组求解（注释的代码也是AC代码）。

代码中 next 存储的是指定位置最长前缀的长度（不是位置）。

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1000009;

string s;
int nex[N], n;
char c[N];

void kmp() {
    n = s.length();

//    for(int i = 1; i <= n; i ++) c[i] = s[i - 1];
//    for(int i = 2, j = 0; i <= n; i ++){
//        while(j > 0 && c[i] != c[j + 1]) j = nex[j];
//        if(c[i] == c[j + 1]) j ++;
//        nex[i] = j;
//    }   return ;

    for(int i = 1, k = 0; i < n; i ++){
        while(k && s[i] != s[k]) k = nex[k - 1];
        if(s[i] == s[k]) k ++;
        nex[i] = k;
    }

}
int main() {
    cin >> s;
    kmp();

    int p = 0;
    for(int i = 0; i < n - 1; i ++)
        if(nex[n - 1] == nex[i]) {
            p = nex[n - 1];
            break;
        }
    if(p == 0) p = nex[nex[n - 1] - 1];
    if(p == 0) cout << "Just a legend";
    else cout << s.substr(0, p);

//    int ans = 0;
//    for(int i = 1; i < n; i ++) {
//        if(nex[i] == nex[n]) {
//            ans = nex[i];
//            break;
//        }
//    }
//    if(ans == 0) ans = nex[nex[n]];
//    if(ans == 0) cout << "Just a legend";
//    else {
//        for(int i = 1; i <= ans; i ++) cout << c[i];
//    }

    return 0;
}