简介

Manacher算法，又叫“马拉车”，它可以在时间复杂度和空间复杂度都是O(n)的情况下，求出一个字符串的最长回文串长度。

回文串常规解法

以每一个点为中心对称点，每次保留最长回文子串的长度，最后得到的就是最长回文子串的长度，但是这样的时间复杂度为O（n^2），并且奇偶回文串是不一样的，奇数的情况下可以遍历每个字符进行中心扩散，偶数的情况下需要遍历每个间隔进行中心扩散。

马拉车

预处理字符串

对于奇偶字符串的处理，manacher采用的是填充特殊字符的方法，并且在字符串两端都加入不同的字符，防止越界（因为不同字符一定不是回文串），比如字符串“abbccbba”，增加字符后变成“^#a#b#b#c#c#b#b#a#$”.

核心算法

重新定义字符串后就是马拉车的核心算法:

在遍历新的字符串之前首先定义两个变量：c，r分别是在已遍历的字符串中最长的一个回文串的中心位置，和他的右边界的位置。用一个数组p来记录每个位置的为中心的最远扩散距离，这个正好也是对应原串中的回文串长度。

在遍历的过程中，首先判断当前位置是否在r之前，如果在的话可以根据回文串强对称性，可以把当前位置的数组p的值继承他对称的位置的值，继承之后再由继承的值进行向两边扩散，最后如果扩散的位置超出r，则更新c和r。

最后便得出了完整的数组p,可以根据此数组得出该串中的最长回文串的长度以及推出该回文串。

示例

P3805 【模板】Manacher

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    string s;
    cin>>s;
    string ns="^";
    for(const char &i:s){
        ns+="#";
        ns+=i;
    }
    ns+="#$";
    ll n=ns.length();
    vector<ll> p(n,0);
    ll c=0,r=0,maxl=1;
    for(ll i=1;i<n;i++){
        if(i<=r){
            p[i]=min(r-i,p[c*2-i]);
        }
        while(ns[i+p[i]+1]==ns[i-1-p[i]]){
            p[i]++;
        }
        if(i+p[i]>r){
            c=i;
            r=p[i]+i;
        }
        maxl=max(maxl,p[i]);
    }
    cout<<maxl;
    return 0;
}