马拉车

标签：start int mid len ss ans 拉车

#include <bits/stdc++.h>
using namespace std;
string s, ss;
int p[100100];
int main(){
    cin >> s;
    ss += "*#";
    int len = s.length();
    for(int i = 0; i < len; i ++)
        ss += s[i], ss += "#";
    len = len * 2 + 2;
    int mid, r = 0, ans;
    ans = -1;
    int start;
    for(int i = 1; i <= len; i ++){
        if(i < r) p[i] = min(p[mid * 2 - i], r - i);
        else p[i] = 1;
        while(ss[i + p[i]] == ss[i - p[i]]) p[i] ++;
        if(i + p[i] > r){
            r = i + p[i];
            mid = i;
        }
        if(ans < p[i] - 1){
            ans = p[i] - 1;
            start = i;
        }
    }
    cout << ans << endl;
    int s = start - p[start] + 1;
    int e = start + p[start] - 1;
    for(int i = s; i <= e;i ++)
        if(ss[i] != '#') cout << ss[i];
    return 0;
} 

 

标签：start,int,mid,len,ss,ans,拉车
From： https://www.cnblogs.com/skadi08/p/16732736.html