四种方法求最长回文串

所谓回文串，就是正着读和倒着读结果都一样的回文字符串。

比如：

a, aba, abccba都是回文串，

ab, abb, abca都不是回文串。

一、暴力法

最容易想到的就是暴力破解，求出每一个子串，之后判断是不是回文，找到最长的那个。

求每一个子串时间复杂度O(N^2)，判断子串是不是回文O(N)，两者是相乘关系，所以时间复杂度为O(N^3)。

运行结果：

二、动态规划

设状态dp[j][i]表示索引j到索引i的子串是否是回文串。则转移方程为：

1.png

则dp[j][i]为true时表示索引j到索引i形成的子串为回文子串，且子串起点索引为j,长度为j+i-1。

算法时间复杂度为O(N ^ 2)。

三、中心扩展法

中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。

需要考虑两种情况：

长度为奇数的回文串，比如a, aba, abcba

长度为偶数的回文串，比如aa, abba

四、Manacher算法

Manacher算法的时间复杂度为O(N)，具体可参考：

https://www.cnblogs.com/grandyang/p/4475985.html