Manacher 算法学习笔记

Manacher 算法于 1975 年发明，用其发明者的名字命名。

Manacher 是一个线性解决回文子串问题的算法。

Manacher 算法适用于处理字符串的所有回文子串，而并非只适用于通常意义上的最长回文子串，具体见下文解释。

前置知识

考虑如何描述一个字符串里的回文子串。

比较简单的想法是记该子串的左右端点，将其记为 \([l,r]\)。
然而对于一个回文子串的子串 \([l+d,r-d]\) 它同样是一个回文子串；
除非我们用较为复杂的方法记录这个回文子串的子串，否则需要用另外的空间来描述和储存，这造成了浪费。

另一个利用回文串性质的记法是记录其对称中心和对称长度。
例如对于字符串 DBABCBAB 中的子串 ABCBC，我们就可以记其为 \([5,3]\)。

对于偶数长度的回文串，我们考虑在每两个字符间插入一个字符，例如 #。
同时我们要在头尾插入一些指示字符，辅助下面算法的判断。
例如把上面的串变成：$D#B#A#B#C#B#A#B。

通过上述记法结合回文串性质可以发现 \([5,2]$,$[5,1]\) 均为回文子串。
我们就可以小改以上这个记法为记录其对称中心和最大对称长度。
也就是说 \([5,3]\) 可以说明以 \(5\) 为对称中心实际上存在 \(3\) 个回文子串。

Manacher 可以用 \(O(n)\) 的复杂度求出每一个对称中心的最长对称长度。
因此，之前说有人对该算法存在误解，其实我们是可以知道所有回文子串的。

算法

考虑一个中心扩展算法。

Unfixed