在刷leetcode时有个求最长回文字符串的问题。

#官方题解提供了4中解决办法，分别是

1.暴力法， 2.动态规划， 3.中心扩展算法， 4.就是我们今天要介绍的Manacher方法。

在介绍算法之前，首先介绍一下什么是回文串，所谓回文串，简单来说就是正着读和反着读都是一样的字符串，比如”aba”，”上海自来水来自海上”等等，一个字符串的最长回文子串即为这个字符串的子串中，是回文串的最长的那个。

阅读全文