manachar （马拉车算法）

回文：

回文的定义十分简单，判断回文串的方法也很简单。对于一个字符串，只需要从他的最中心向两边扩展就足够了，可以将它称之为中心扩展法，我们的马拉车算法也是从中心扩展法扩展而来。

马拉车算法的运用之处：

对于一个字符串，询问它的字串中长度最大的回文串的长度。

显然，我们可以暴力求解：
遍历这个字符串，对于其中每个字符，都通过中心扩展法来求出以当前字符为中心的回文串的长度，最后求最大值。当然这只能奇长度的回文串，如aba，若为abba，则需要用连续的两个字符向两端扩展。这个解法的时间复杂度在字串内的回文串数较多时能达到$O(N^2)$的时间复杂度。那么怎么样才能够更快呢？

这时就是用到马拉车算法的时候了。（其实马拉车算法一般在OI中用的应该不多，至少我这个蒟蒻是没怎么看到过）。

马拉车算法原理

显然，一个回文串具有对称性的特点，那么我们可以提前通过这个回文串的对称性来提前确认以某个字符为中心的回文串中的某一段回文串的可能的长度。(类似于贪心？)在之后遇到该字符时通过该长度继续扩展即可。具体看例子。

由于要以某个字符串为中心扩展，所以只有在回文串为奇长度时才能使用。

例如(第一行为字符串，第二行为以该字符串中该字符为中心的回文串的长度，第三行为其下标)：

字串$abababa$

长度$1357531$

下标$1234567$

我们可以发现，由于回文串的对称性，在这个回文串中，以中心为对称轴，以其两边字符为中心的回文串长度是相同的，如以下标为3或与下标为5的字符串为中心的回文串长度是相同的，2和6，1和7同理。因此我们可以通过对称性来提前确认以该字符为中心的可能的回文串长度，之后再进行扩展。

由于要以某一字符为中心，所以只有奇长度的回文串才可以如aba可以，abba则无法进行，于是我们就需要将该字符串进行变化使得它的回文串从偶长度变为奇长度后再进行。

算法的代码实现

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;
const int N=1e6+10;
char a[N];
char b[N<<1];
int l,ans;
int len[N<<1];
void change(){
    memset(b,0,sizeof b);
    l=strlen(a);
    b[0]='<';
    for(int i=0;i<l;i++){
        b[i*2+1]='#';
        b[i*2+2]=a[i];
    }
    l=l*2+2;
    b[l-1]='#';
    b[l]='>';
}
void manachar(){
    memset(len,0x3f,sizeof len);
    ans=1;
    int r=0,m=0;
    for(int i=1;i<l;i++){
        if(i<r){
            len[i]=min(len[2*m-i],r-i);
        }
        else{
            len[i]=0;
        }
        while(b[i+len[i]+1]==b[i-len[i]-1])len[i]++;
        if(len[i]+i>r) r=len[i]+i,m=i;
        ans=max(ans,len[i]);
    }
}

int main(){
    while(cin>>a){
        change();
        manachar();
        cout<<ans<<endl;
    }
}

总结

在实际运行中，我们可以发现，这个算法在字符串中回文串数量较多时是比较快的，对于字符串中回文串数量较小的话，这个算法较暴力写法还是比较一般的。因此一般这个算法用不怎么到。（我个人的理解是把这个算法看成一个贪心算法）。