manacher

· · 个人记录 

void manacher(char s[],int n,int p[])
{
    int l=0,r=0;
    for(int i=0;i<n;++i)
    {
        if(r<i)l=r=i;
        p[i]=min(r-i,p[l+r-i]);
        while(i-p[i]>=0&&i+p[i]<n&&s[i-p[i]]==s[i+p[i]])++p[i];
        if(i+p[i]>r)r=i+p[i],l=i-p[i];
        if(p[i]-1>ans)ans=p[i]-1;
    }
}

分析：

  1. 一般用 manacher 解决问题的时候，我们在每个字符之间插入一个‘#’

比如对于字符串\tt abc，我们会把他变成\tt \#a\#b\#c\#

记原串为S,插入了'#'的串为T

  1. p[i]表示从i点出发，往一个单方向最长的长度，使得这个串是回文串。

说起来有点绕，举个例子，对于串\tt abcba，\tt c所在的位置的p值为3,即字符串\tt abc或者\tt cba的长度。

  1. 这里的l,r是开区间，表示一个回文串的区间。

  2. 为什么\tt p[i]=min(r-i,p[l+r-i])？

对于\tt r-i，由于l,r表示的是开区间，所以继承以前回文串留下来的信息最多只能到\tt r-i

  1. 注意一定要判边界，不要数组下标越界(\tt i-p[i]>=0\&\&i+p[i]<n)

  2. 由于我们跑 manacher 的串是插入了'#'的，所以p[i]-1即为原串中回文串的长度

如果T_i是一个字母的话，说明这是一个长度为奇数的回文串。否则，若T_i是‘#’的话，说明这是一个长度为偶数的回文串。

为什么p[i]-1是表示原串中的回文串长度呢？

不妨分类讨论：

\tt X\#X\#……X\#

或

\tt \#X……\#X\#X

（这里的'X'表示某个字母）

根据刚才的结论，因为T_i是一个字母，所以在对应的原串中，这是一个长度为奇数的回文串。

显然，‘X’的数量与‘#’的数量相同，所以此时的p[i]的数值等于：一个长度为奇数的回文串中包括了中间那个字符的那一半的字符串的长度的两倍。 （比如说对于原串\tt abcba，字符\tt c对应的p值即为字符串\tt cba或\tt abc长度的两倍）。

由于这个p值的计算相当于把中间的字符多算了一遍，所以对应的原串中回文串的长度为p[i]-1。

此时，对应的原串是一个长度为偶数的回文字符串，记这个回文字符串为A。

显然，此时'#'的数量比'X'的数量多了1，又因为这是一个长度为偶数的回文串，所以p[i]对应的那一段字符串中字母的个数恰为原串中对应的回文字符串的长度的一半。

由于\tt p[i]=num('\#')+num('X'),且\tt num('\#')=num('X')+1, |A| =\tt2*num('X')

所以|A| \tt =p[i]-1

  1. 如果题目中要让我们求长度为奇数的回文字符串的话，那么我们不用插入'#'，直接跑 manacher 就行了