给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。如"abc"有三个回文子串‘a','b','c'.

示例 1：

输入："abc" 输出：3 解释：三个回文子串: "a", "b", "c"

示例 2：

输入："aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

对于这个问题，简单的思路是枚举字符串中的每个子串，然后判断子串中回文串的个数。O(N^3)

本篇文章主要介绍我个人对马拉车算法实现思路的一些想法，原题解请看leetcode-647.回文子串

由于回文串有对称性这一特点，每个回文串必然存在一个对称中心。我们可以对字符串中每个字符或两个字符之间的位置(若回文串长度为偶数)当作对称中心进行枚举,例如s="abcba",当i=2时，判断a[1]==a[3],a[0]==a[4].....如果左右两边字符相同时则继续扩展，一旦不相同则更新最大扩展长度并退出当前循环，继续枚举下一个对称中心。

假设字符串的长度为 n，枚举每个对称中心(长度为 1 和 0的对称中心分别有 n 和 n-1 个)，共遍历2n-1次，时间复杂度为 O(n)；每个对称中心最多向外拓展n次，所以整体的时间复杂度是 O(n^2)。空间复杂度为O(1)。

代码如下(直接抄leetcode了):

还有没有优化的空间呢？让我们看看在中心拓展法中出现的两个问题，然后了解一下马拉车算法如何对这两个问题进行处理。

为了更简单直接地说明问题，我举一个极端的特例:字符串s="aaaaaaa"，并先对奇回文子串进行查找。尽管我们在以第2位字符为对称中心左右扩展时能够发现左回文子串s1="aaa"，并且以第四位字符为对称中心左右扩展能够发现了长回文串s，那么之后的查找中是否仍需要匹配后三位字符串呢？设Im为长回文串的对称中心

其实，我们可以发现，若在一个长回文串中发现了左回文子串，根据回文串的对称性，那么在一定区域内的右子串中必然也存在一个回文串。因此，上述重复查找过程是可以省去的。

马拉车算法的核心思路就在于，对每个长回文串的对称中心向两边进行拓展，同时记下前面已经查找过的回文子串半径(原理是动态规划的思想)，其本质在于，如果能够找到一个长回文串，同时在它的对称中心左区域中找到一个回文子串，由于回文串的对称性，其右区域中必然是同样的回文子串。因此这个算法能快速地找出最长的回文子串。当然也能用来求解回文子串的个数。

1.预处理(解决了奇偶回文串问题)：

预处理代码如下

2.初始化(解决了重复查找问题):

初始化：

以字符串"dadbdac"为例

这里有两种情况:

Case 1:  ir-i时，通过d加速拓展的右子串超出了长回文串的范围。然而大于右端点的回文串我们还没有开始匹配，此时d[i] = r - i . 比方说，当Im=3时,有r=5;当i=5时,有j=1,并且前面已经算出d[j] = 1。此时d[j]>r-i，向右拓展超出了长回文串范围，则d[i]应为i到右端点r的距离,即r-i。因此，当对称中心i被包含在当前最大回文串内时，有

d[i]=min(d[2 * Im - i],r - i) （核心：如果d[j]+ir，此时用常规的中心拓展法更新d[]、Im以及r。

3.中心拓展：

经过了上面的初始化，我们每次枚举对称中心的时候就都能够保证 s[i-d[i]]=s[i+d[i]]，而现在，只要再满足ts[i - d[i]-1]==ts[i + d[i]+1]，则不断向左右两边拓展半径。

综上所述，我们能够写出马拉车算法的核心代码：

顺带提一句，最开始我以为马拉车这个算法名字应该是根据Manacher英译而来，但是这个中心扩展的思路，加上通过d[i]记录了最大回文串的半径避免了重复匹配，光看这两行代码：

真是有两头马在拉着一个对称中心向两边跑的感觉，大概就像这样：

然后不断更新最大回文串的对称中心Im和 r，通过d[i] = min(d[2 * Im - i], r - i)快速求解

如何求解ans就不解释啦，直接上代码: