最长回文子串

最长回文子串（英语：Longest palindromic substring）是计算机科学中的问题，在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如“abracadabra”，没有超过3的回文子串，但是有两个回文字符串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。

Manacher于1975年发现了一种线性时间算法，可以在列出给定字符串中从任意位置开始的所有回文子串。并且，Apostolico, Breslauer & Galil 发现，同样的算法也可以在任意位置查找全部极大回文子串，并且时间复杂度是线性的。因此，他们提供了一种时间复杂度为线性的最长回文子串解法。另外，Jeuring (1994), Gusfield (1997)发现了基于后缀树的算法。也存在已知的高效并行算法。

最长回文子串算法不应当与最长回文子序列算法混淆。

如果一个长度为 ${\displaystyle n}$ 的字符串 ${\displaystyle s}$ 当中所有字符依次为 ${\displaystyle s_0,s_1,s_2\cdots <!--\; \cdots \; -->s_{n-<!--\; -\; -->1}}$. 且 ${\displaystyle s}$ 满足 ${\displaystyle \mathrm{\forall <!--\; \forall \; -->}i\in <!--\; \in \; -->,s_i=s_{n-<!--\; -\; -->i-<!--\; -\; -->1}}$, 那么则称 ${\displaystyle s}$ 为一个回文字符串。

如果字符串 ${\displaystyle s}$ 的一个回文子串 ${\displaystyle s_1}$ 是 ${\displaystyle s}$ 所有回文子串中长度最长的，那么则称 ${\displaystyle s_1}$ 为 ${\displaystyle s}$ 的最长回文子串。

在了解Manacher算法之前，我们先了解一下“笨”办法，也就是暴力循环，或者说死算。

注意到每个回文字符串都是以一个对称点为中心左右对称的，所以暴力运算的方式是我们循环每个字母作对称点，然后在每个对称点查看所能找到的最大回文字符串的长度，最终得到结果。

需要注意到的一点，就是如果单纯的把每个字符当作对称点的话，只能得到奇数长度的回文字符串符。而回文字符串可能是偶数长度的，比如“cbaabd”中的“baab”，此时对称点是介于两个字符“a”中间的。这样的话，如果直接处理起来，可能会比较麻烦，比如需要额外定义如何表示字符中间的位置。

这里有一种巧妙的办法，就是在字符串中插入一些定位符，比如“$”，比如字符串“cbaabd”就会变成“$c$b$a$a$b$d$”。

此时我们只需要按照奇长度字符串的处理方式去处理这个字符串（即每次选取对称点只需依次选取字符），最后得到的回文字符串“$b$a$a$b$”中，再把定位符“$”去掉，我们就可以得到原始的偶长度字符串“baab”了。

将输入字符串s插入定位符，比如"$"定义一个数组P，用于存储以i位置为对称中心的最长回文字符串的“半径”for c = 0 to len(s) do    // 找到最长回文字符串“半径”    r = 0    while c-(r+1) >= 0 and c+(r+1) < len(s) and s == s do        r = r + 1    end while    p = rend for找到P中的最大值P取出返回字符串 ret = substring(s, x-P, x+P)将ret字符串中的定位符去除return ret