CF126B Password

题目传送门

解题思路:

先跑一遍KMP,维护出不包括题目所给串(暂且称他文本串)本身的其他串中最大的最长公共前后缀(mm),然后找文本串的公共前后缀中小于mm最大的那一个(u),如果长度为0,说明没答案,如果不为0,则前mm个字符即为答案,感性证明一下,mm不为0说在中间有一部分与开头匹配,且长度1~mm都是可以找到匹配方案的,如果最后找到的u大于零,说明最后u位于最开头的u位可以匹配,而最开头的u位于中间有匹配方案,所以就满足了答案条件.

AC代码:

#include<iostream>
#include<cstdio>

using namespace std;

string l,p;
int kmp[1000001],j,mm;
bool flag;

inline int max(int a,int b) {
    if(a > b) return a;
    return b;
}

int main() {
    cin >> p;
    l = " " + p;
    int n = l.length() - 1;
    for(int i = 2;i <= n; i++) {
        while(j != 0 && l[i] != l[j+1]) j = kmp[j];
        if(l[i] == l[j+1]) j++;
        kmp[i] = j;
        if(i != n) mm = max(mm,kmp[i]);
    }
    int u = kmp[n];
    while(u > mm) u = kmp[u];
    if(u == 0) {
        printf("Just a legend");
        return 0;
    }
    for(int i = 1;i <= u; i++)
        cout << l[i];
    return 0;
}