马拉车Manacher

解决的问题：求最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
typedef int ll;

struct Manacher{
    vector<ll> v,p; // 原数组/预处理后的数组
    vector<ll> f; // 回文半径数组：f[i]表示以i为中心的回文串的半径
    ll n; // 预处理后的数组长度
    void solve(){
        n=v.size()*2+1;
        p.emplace_back(0);
        for(ll i=0;i<v.size();i++){
            p.emplace_back(v[i]);
            p.emplace_back(0);
        }
        f.resize(n,0);
        for(ll i=0,j=0;i<n;i++){
            if(2*j-i>=0&&j+f[j]>i) f[i]=min(j+f[j]-i,f[2*j-i]);
            while(i-f[i]>=0&&i+f[i]<n&&p[i-f[i]]==p[i+f[i]]) f[i]++;
            if(i+f[i]>j+f[j]) j=i;
        }
    }
    Manacher(vector<ll> &_v):v(_v){solve();}
    Manacher(string &s){
        v.resize(s.size());
        for(ll i=0;i<s.size();i++) v[i]=s[i];
        solve();
    }
    ll operator[](ll x){return f[x];}
};

int main(){
    string s;
    cin>>s;
    Manacher manacher(s);
    ll ans=0;
    for(ll i=0;i<manacher.n;i++) ans=max(ans,manacher[i]);
    cout<<ans-1<<endl;
    return 0;
}