主题：

给出字符串s，找出s中最长的回文部分串。 可以假设s的最大长度为1000。

示例1 :

输入3360“黑板”

输出： 'bab '

请注意， 'aba '也是有效的答案。

示例2 :

输入： 'cbbd”

输出： 'bb ' '

分析

首先什么是回文字符串？ 回文字符串是指字符串整体以中心轴为中心对称的字符串。 例如，“abcdcba”和“abba”都是回文字符串。 的字符串和长度为1的字符串都毫无疑问是回文字符串。

要判断字符串是否为回文字符串，只要从字符串的正中央向两侧扫描，判断对应位置的字符相等即可。 字符串长度为奇数时，最中间的字符为开始位置，字符串长度为偶数时，最中间的两个字符为开始位置。

要在

最笨的解法

字符串中找到最大的回文子串，肯定是最愚蠢的方法，最容易想到的方法是循环扫描。 可以遍历以字符串中每个字符为中心的回文子串，以找到所有这些子串中最长的。 这种傻逼方法的时间复杂度为o(n^2)。

实现代码如下：

利用数组缓存回文状态

上面的方法是用双重循环遍历所有回文字符串，比较他们的长度，从而找出最长的。 也可以创建二维数组temp[][]。 temp[i][j]表示区间[j，i]是否为回文字符串。 那么，有以下递归。

由于i==j时表示单个字符，因此temp[i][j]=true； 因为i==j 1时表示邻接字符，所以有I，j字符相等时为temp[i][j]=true，否则为temp[i][j]=false； 在I 1的情况下，只需要知道区间[j 1，i - 1]是否是回文字符串，否则temp[i][j]肯定不是，如果是，则判断I，J1字符串是否相等。 基于上述递归实现的代码如下。

字符串“babad”的执行步骤如下所示。

O(n)的解法

第一个方法是用双重循环求解，所以时间复杂度一定是o(n^2)。 第二种方法也有双层循环，虽然内循环不是完全的n，但时间复杂度仍为o(n^2)。

那么，有时间复杂度为o(n )的解法吗？ 很明显有。

实现的代码如下所示。

该实现方式使用的是马拉色算法(Manacher's Algorithm )。 具体的计算过程稍后有时间的话会详细介绍。