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

谁是鸽王

2018-10-22 19:52:55

题解

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

UPD20220319:改进排版

UPD20190927:重置代码，规范边界

UPD20190712:删除了一些愤怒的话语，精炼了语言，添加了LaTex。

看到个别教程，我猜他们大都是自己背的模板。不知所云。对于manacher的核心根本就没有说明，只是对于核心的代码进行强调。到头来必须自己领悟。

我们先看两个字符串：

ABCCBA

ABCDCBA

显然这两字符串是回文的

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

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

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

(注意到我们这里还插入了一个“～”，原因在代码里说明，不了解这里没有任何关系)

manacher为什么有如此优秀的复杂度呢？让我用文字说明一下

对于一个回文串，有且仅有一个对称中心。且叫它回文对称中心。
在一个回文串内，任选一段区间 X ，一定存在关于"回文对称中心"对称的一个区间 Y ，且把这个区间 Y 叫做关于区间 X 的对称区间。
区间和对称区间一定全等。(你都是对称的怎么可能不全等)
若一个区间的对称区间是回文串，这个区间必定是一个回文串。在大的回文串内，它们回文半径相等。
然而我们通过确定关系预先得到的回文半径，它的数值，必定小于等于这个位置真实的回文串半径。

因此，我们若记录以每个位置为中心的回文串半径，当我们通过另一个回文中心将这个原先的中心点对称过去时，就可以确定对称过去的那个点的回文半径了。

考虑"另一个回文中心"如何确定，就是那个极大回文串的回文中心，也就是边界顶着右边我们已知的最远位置的，最长的回文串。

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

记录这些数据到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是难以学习的算法。至少当我在学习的时候，是一头雾水。

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

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

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

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

最终答案是

    P(max)-1

假设原串某个最长回文串长度为L，在新串里的长度将会是2L+1，回文半径将会是L+1，而L+1=P(max)那么答案就是P(max)-1了

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

//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=11000002;
char data[maxn<<1];
int p[maxn<<1],cnt,ans;
inline void qr(){
      char c=getchar();
      data[0]='~',data[cnt=1]='|';
      while(c<'a'||c>'z') c=getchar();
      while(c>='a'&&c<='z') data[++cnt]=c,data[++cnt]='|',c=getchar();
}
int main(){
      qr();
      for(int t=1,r=0,mid=0;t<=cnt;++t){
        if(t<=r) p[t]=min(p[(mid<<1)-t],r-t+1);
        while(data[t-p[t]]==data[t+p[t]]) ++p[t];
        //暴力拓展左右两侧,当t-p[t]==0时，由于data[0]是'~'，自动停止。故不会下标溢出。
        //假若我这里成功暴力扩展了，就意味着到时候r会单调递增，所以manacher是线性的。
        if(p[t]+t>r) r=p[t]+t-1,mid=t;
        //更新mid和r,保持r是最右的才能保证我们提前确定的部分回文半径尽量多。
        if(p[t]>ans) ans=p[t];
      }
      printf("%d\n",ans-1);
      return 0;
}

祝大家学习愉快。

2022:博主现在在上海某一流大学CS专业就读, 每次打开洛谷总能看见这篇题解或赞增加; 或来了一两句不友善的评论。其实我都能理解，这篇题解最初发布于2018年，四年之久，我相信OI题解的环境发生了好的变化，再也看不到四年前互联网上屎一样的教程了。但是我决定将当年说的那些话保留下来，一个是保存我青春的回忆，另一个是希望让大家在有时枯燥的OI生活中找到一个对线的对象。