nmnnmn

元始天尊

2026-07-02 19:55:21

发布于：浙江

3阅读

0回复

0点赞

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int P = 13331;
const int N = 1000010;
string s;
ull p[N] , h[N];
bool a[N];
ull get(int l , int r){
    return h[r] - h[l - 1] * p[r - l + 1];
} 

bool check(int i , int mid){
    return get(i , mid) == get(i , s.size());
}

int main(){
    cin >> s;
    p[0] = 1;
    for(int i = 1;i <= s.size();i++){
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + s[i - 1];
    }
    int maxv = 0;
    for(int i = 1;i < s.size();i++){
        int l = 0 , r = s.size() - i;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(!check(i , mid)) r = mid - 1;
            else l = mid;
        }
        maxv = max(maxv , l);
    }
    for(int i = maxv;i >= 1;i--){
        if(get(1 , i) == get(s.size() - i + 1 , s.size())){
            for(int j = 0;j < i;j++){
                cout << s[j];
            } 
            return 0;
        }
    }
    cout << "Just a legend";
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论