P3805 manacher算法

题目地址：https://www.luogu.com.cn/problem/P3805

思路

马拉车其实就是每次算某个点的回文半径到时候，会看自身是否处在一个之前求过的回文串T中，然后根据镜面对称，O(1)获取以自己为中心在T中的最大回文子串,然后再尝试暴力，所有的更新暴力复杂度为O(n)

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e7+2e6 + 10;//没错这题有512MB内存,这里最多会用到300MB
using namespace std;

string s;
int ans[maxn],str[maxn],lef[maxn];
int build(const string &s){
    int n = s.length(), m = (n + 1)*2, ret = 0;
    str[0] = '$'; str[m] = '@'; str[1] = '#'; ans[1] = 1;
    for (int i = 1; i <= n; i++) 
        str[i*2] = s[i - 1], str[i*2+1] = '#';
    ans[1] = 1;
    for (int r = 0, p = 0, i = 2; i < m; ++i){
        if (r > i) ans[i] = min(r - i, ans[p * 2 - i]); 
        else ans[i] = 1; 
        while(str[i - ans[i]] == str[i + ans[i]]) ++ans[i];
        if (i + ans[i] > r) r = i + ans[i], p = i;
        ret = max(ret, ans[i] - 1);
    }
    return ret;
}

int main(){
    ios;
    cin>>s;
    int res = build(s);
    cout<<res<<endl;
    return 0;
}