Manacher 回文串子串

因为 Manacher 的题目不是很多,所以直接放到杂题来了。

Manacher 用于解决有关字符串的回文子串的问题。如:计算字符串中回文子串个数,字符串中的最长回文子串长度。以计算回文子串个数为例,朴素算法 O(n3)O(n^3),枚举会回文中心向外暴力枚举复杂度 O(n2)O(n^2),字符串哈希做到 O(nlogn)O(n\log n),Manacher 能在 O(n)O(n) 时间复杂度内解决该问题。

我们仅考虑奇回文串,即回文中心在字符上,令 did_i 表示对称中心在 ii 位置的回文串的最大回文半径。在处理 did_i 时,我们已经处理了所有 j<ij<i 的值 djd_j,我们设现在右端点最右的回文串位置为 [l,r][l,r],初始时 l=0,r=1l=0,r=-1。在计算 did_i 时,我们尽可能利用已知信息去推到新的信息。进行如下的分类讨论:

  • i>ri>r,那么就直接暴力扩展。

  • iri\le r,继续分类,我们找出 ii 关于 [l,r][l,r] 这一个回文子串的回文中心对应的位置为 j=l+rij=l+r-i

    • i+dj1<ri+d_j-1<r,那么必然无法继续向两侧扩展,则 di=djd_i=d_j

    • i+dj1ri+d_j-1\ge r,那么先令 di=ri+1d_i=r-i+1,在暴力向右扩展。

偶回文串同理。我们发现每一次迭代计算 rr 只会向右移动,不会向左,因此 rr 的移动次数是 O(n)O(n) 的。因此复杂度是 O(n)O(n)

对于偶回文串,有一种更加方便的处理方法:在相邻两个字符之间插入字符 #(即一种未在字符串中出现的字符),这样就能把偶回文串转化为奇回文串处理了。代码如下:

for(int i=0,l=0,r=-1;i<n;i++){
int k=(i>r)?1:min(d[l+r-i],r-i+1);
while(0<=i-k&&i+k<n&&s[i-k]==s[i+k]) k++;
d[i]=k--;
if(i+k>r) l=i-k,r=i+k;
}