Manacher 回文串子串
因为 Manacher 的题目不是很多,所以直接放到杂题来了。
Manacher 用于解决有关字符串的回文子串的问题。如:计算字符串中回文子串个数,字符串中的最长回文子串长度。以计算回文子串个数为例,朴素算法 ,枚举会回文中心向外暴力枚举复杂度 ,字符串哈希做到 ,Manacher 能在 时间复杂度内解决该问题。
我们仅考虑奇回文串,即回文中心在字符上,令 表示对称中心在 位置的回文串的最大回文半径。在处理 时,我们已经处理了所有 的值 ,我们设现在右端点最右的回文串位置为 ,初始时 。在计算 时,我们尽可能利用已知信息去推到新的信息。进行如下的分类讨论:
-
若 ,那么就直接暴力扩展。
-
若 ,继续分类,我们找出 关于 这一个回文子串的回文中心对应的位置为 。
-
若 ,那么必然无法继续向两侧扩展,则 。
-
若 ,那么先令 ,在暴力向右扩展。
-
偶回文串同理。我们发现每一次迭代计算 只会向右移动,不会向左,因此 的移动次数是 的。因此复杂度是 。
对于偶回文串,有一种更加方便的处理方法:在相邻两个字符之间插入字符 #
(即一种未在字符串中出现的字符),这样就能把偶回文串转化为奇回文串处理了。代码如下:
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;
}