题解 P3805 【【模板】manacher算法】

我们先看两个字符串：

ABCCBA

ABCDCBA

显然这两字符串是回文的

然而两个串的对称中心的特性不同，第一个串，它的对称中心在两个C中间，然而第二个串，它的对称中心就是D。这样我们如果要记录回文串的对称中心，就显得复杂了。

为了解决这个问题，把两种情况统一起来，我们就在字母之间插入隔板，这样两个问题就统一了，因为所有的对称中心都会有个字符与之对应。像这样

~A|B|C|C|B|A|

（注意到我们这里还插入了一个“～”，原因我们待会说明）

manacher为什么有如此优秀的复杂度呢？让我用比图片还要清楚的文字说明一下

对于一个回文串，有且仅有一个对称中心。且叫它回文对称中心。
在一个回文串内，任选一段区间 X ，一定存在关于”回文对称中心“对称的一个区间，且把这个区间叫做关于区间_X_的对称区间。
区间和对称区间一定全等。（ 1）(十分显然)
由_（1）得 ,若一个区间的对称区间是回文串，这个区间必定是一个回文串。在大的回文串内，它们回文半径相等。 (2)_
然而我们通过确定关系预先得到的回文半径，它的数值，必定小于等于这个位置真实的回文串半径。（十分显然）

因此，为利用特性（2），我们若记录每个字符作为回文对称中心时的回文串的半径，就可以知道该字符，它，关于某另一个对称中心（称此对称中心对应的回文串叫做“大回文串“）对称的，在大的回文半径内，对应字符的部分回文半径了。

记录这些数据到p数组。同时记录一个mid，一个r，分别代表 已经确定的右侧最靠右的回文串的对称中心和右边界

然而，考虑一些情况，发现我们只能确认我们已知的回文串内的对称关系和回文半径等量关系，关于这个大回文串右侧的世界，我们一无所知。

那么，当我们扫描到一个新的字符时，怎么先确定它的部分回文半径呢？

若当前扫描到的位置为i，若mid<=i<=r，则我们可以找到它的一个对称点。这个点的位置是多少？是mid×2-i。我们现在对其推导一下。

设：这个新点位置为i，它关于mid对称的点为j，将整个字符串看做以下标0位置为原点的数轴，我们由中点公式可得：

( i + j ) / 2 = mid

方程两边同时乘以二, 得：

i + j = 2 * mid

移项，得：

j=2*mid-i

证毕。

就是这样小学生都会的推导过程，几乎每篇题解都是直接摆出结论，不给出证明和推导，要求学习者自己”找规律” ，我真是不敢苟同。希望大家以后发题解要严谨一点，至少自己没有真正理解就不要发题解，让人觉得manacher是难以学习的算法。至少当我在学习的时候，是一头雾水。

所以，拓展一个新点时，我们不必从这个点左右两边第一个位置开始向两边拓展，可以预先确定一部分回文串。就是因为这个，manacher的复杂度是线性的。

若扩展一个新的关于该字符的回文半径，可以先确定一部分P[i]。
且我们知道，我们能确定的范围，其右侧不得大于r，即：p[i]+i<=r 移项得：p[i] <= r-i

故此，要取一个min 这里给出代码:

	P[i]=min(P[mid*2-i],r-i)

最终答案是

	P(max)-1

讲到这里，应该十分清楚了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=11000002;

char data[maxn<<1];

int p[maxn<<1];

int cnt=1;

#define RP(t,a,b) for(int t=(a),edd=(b);t<=edd;t++)

inline void qr(){

    char c=getchar();

    data[0]='~';

    data[1]='|';

    while(c<'a'||c>'z')

        c=getchar();

    while(c>='a'&&c<='z'){

        data[++cnt]=c;

        data[++cnt]='|';

        c=getchar();

    }

    return;

}

int maxans,rb,mid;

inline int cmpless(int x,int y){

    if(x<y)

        return x;

    return y;

}

int main(){

    //freopen("in.in","r",stdin);

    //freopen("out.out","w",stdout);

    qr();

    RP(t,1,cnt){

        if(t<rb)

            p[t]=cmpless(p[(mid<<1)-t],rb-t);

        else

            p[t]=1;

        while(data[t-p[t]]==data[t+p[t]])

        //暴力拓展左右两侧,当t-p[t]==0时，由于data[0]是'~'，自动停止。

        //故不会下标溢出。

            p[t]++;

        if(p[t]+t>rb)

        //更新mid和rb,保持rb是最右的才能保证我们提前确定的部分回文半径尽量多。

            rb=p[t]+t,mid=t;

        if(p[t]>maxans)

            maxans=p[t];

    }

    cout<<maxans-1<<endl;

    return 0;

}

祝大家学习愉快

巴特西

题解 P3805 【【模板】manacher算法】