字符串哈希与杂题

Manacher 回文串子串

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

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

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

• 若 $i>r$，那么就直接暴力扩展。

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

  • 若 $i+d_j-1<r$，那么必然无法继续向两侧扩展，则 $d_i=d_j$。

  • 若 $i+d_j-1\ge r$，那么先令 $d_i=r-i+1$，在暴力向右扩展。

偶回文串同理。我们发现每一次迭代计算 $r$ 只会向右移动，不会向左，因此 $r$ 的移动次数是 $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;
}