Manacher算法

用途：用于在线性时间内求解回文字符串相关的问题，如找出最长回文串，找出所有回文串个数等。

回文字符串并不是回族人写的字，而是指正反读都一样的句子，上海自自来水来自海上，就是一个经典的回文字符串，还有号称千年一遇的20200202，20211202，20300302，20400402，20500502。

基本思想是利用计算过的信息来更新当前信息，可以说是“以史为鉴”，也就是过去发生的事情对当下有一定的启示作用。

我们遍历所有的位置[i]，计算以此为中点的最长回文子串的半径，记为p[i]，如果半径是0，代表只有本身，如果半径是2，回文串长度就是3。比如"abc"以b为中点的最长回文字符串的半径是1，以a为中点的最长回文字符串就是本身，所以它的半径是0.

由于"aa"这样的字符串也是回文字符串，而它的中点位置不是整数，为此我们首先扩充数组，在每两个元素以及开头和结尾插入一个特殊的符号，比如#，如果原始字符串为"aab"，插入后变成"#a#a#b#"，转换关系是这样的：后来的下标除以2（向下取整），得到原始下标，这一性质有助于我们恢复原始信息。在填充完成后，我们就可以开始遍历所有的i（注意这里仍是中点的意思）。

还有一点需要说明：遍历到 i 的时候，前 i-1 个元素的结果都有了，所以可以利用这一结果，假设在前i-1位置上，C为右边界最靠右的回文子串的中心位置，R为其右边界；（意思是这样的，在已经处理过的位置中，有一些回文字符串，它们的右边界有很多位置，在这之中，我们选择右边界最靠右的这个回文字符串，设它的右边界位置为R，它的中心位置为C）

这是已知的信息：（标上了L是为了便于说明，L和R关于C对称）

    L       	C           R
s0, s1, s2, s3, s4, s5, s6, s7 s8, s9

现在来看我们要处理的位置i , 首先i肯定是在C的右边的，不然不可能有C的结果，下面分为两大类，四种情况来进行讨论：

首先第一大类，处理的 i 元素位于R的左边（可以和R重合），如下图所示：

由于我们不知道 i 的信息，但我们知道所有 i 之前的信息，其中一个比较重要的就是i 关于 C位置对称点 2C - i 处，它的半径长度是p[2C - i]，这个位置肯定是位于L和C之间的（L是以C为中点的回文串的左边界），我们需要分析的是2C-i的左边界和L的关系:

(a) 2C-i的左边界在L的右边图中的蓝色圆圈代表的是回文串的位置，用圆画出以表明其边界和对称性。此时在i位置处也一定存在一个半径为p[2C - i]，为什么？因为对称，2C-i身边有的，i都有，为什么一定都有呢，因为2C-i的半径还在L和R中，所以左半边有的，右半边一定有同样一份。这样一来，我们要更新i位置处的长度时，就可以直接从p[2C - i]的值开始，而不必从0开始。

(b) 2C-i的左边界等于L 和(a)的情况是一样的，因为还是没有超过L，所以i处的值p[i]依然可以从p[2C - i] 值开始，而不必从0开始。

(c) 2C-i的左边界在L的左边如果超出了L，如图C所示，是不是至少还有和对称位置一样的回文串呢？这时候就未必了，假设有的话，那就是红颜色的圈，图中的m是L左边的一个位置的值，它关于2C-i的对称点为n，且m=n。n关于C的对称点为s，且n=s。假设在i处也有的话，设对称点为t，且有s=t。所以得到m=n=s=t，也就是m=t。

而根据对称性，这个t位置显然是R的右边一个，这说明以C为中点的回文字符串长度可以增加1，右边界R可以扩展到R+1位置，这显然是不行的，因为我们之前的假设是R是最靠右的，现在又出来个比它更靠右的，矛盾了。所以在i位置处一定不可能有那么大的红圈。

但是小一点还是可以的，只要保证在R的范围内，那么这个长度就是R-i，所以在这种情况下，p[i]也不必从0开始，而是从R-i开始。

上面的情况可以归结为如下代码：

if i <= R:
	p[i] = min(p[2 * C - i], R - i)

综上，在这些情况下，我们可以利用原有信息，计算新值的时候，不必从头开始，这样就省了很多事，也就是以史为鉴的意思。如果忘记了过去的信息，对于每个位置都要将半径从0开始，一个一个试。

下面来看第二种情况：i在R的左边

这时候就无法利用原有信息，太过分了，超出了历史可以理解的范围，所以就从头开始自己慢慢试。所以先认为 p[i] 从0开始，然后尝试能否扩张它的边界。

上面的四种情况，实际上只是为了在计算p[i]时，给它一个初始值，而不是最终结果，最终的结果要在此基础上，尝试看看能不能扩大一些，扩大的过程是这样的：对于一个位置i看它的i+p[i]+1 位置和i-p[i]-1位置是否相等，如果相等，就再继续看下一个，这样循环下去。还有对于每一个新的i位置的结果，要看看右边界是否超过R，超过R就要更新C和R，因为要保持C和R始终是最靠右的那个字符串的信息。

下面给出完整的代码：

def countSubstrings(self, s):
    s = '#' + "#".join(s) + '#'
    n = len(s)
    p = [0] * n

    C, R, rad = 0, -1, 0
    for i in range(n):
        if i <= R:
            rad = min(p[2 * C - i], R - i)
        while i + rad + 1 < n and i - rad - 1 >= 0 and s[i + rad + 1] == s[i - rad - 1]:
            rad += 1
            
        p[i] = rad
        if i + rad > R:
            R, C = i + rad, i
    return p

这里没有进行任何处理，只是构造出了这样一个数组，具体的操作就要看具体的应用了；比如输入"aba"，这里的p数组是这样的：

[0, 1, 0, 3, 0, 1, 0]

这是被填充过#的数组，所以长度长了一些，比如题目问的是求最长的回文串长度，只要找到这里面的最大值就可以了，长度是3，就是"aba"本身。为什么就是这里面最大的呢，这里的p虽然是半径数组，但是我们原始的填充相当于给数组扩大了两倍，这样一来就刚刚好了。