线性时间求最长回文子串

一般来说，解决字符串问题可用穷举法，找回文子串需要3层循环，时间复杂度O(n^3)，这是无法接受的。

回文子串显然符合以下特点：1.重叠子问题。2.最优子结构，动态规划可解之，复杂度O(n^2)，还不错。

重点介绍的是Manacher算法，leetcode有一篇讲解非常仔细：

http://articles.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

算法很短，精要之处也就2、3行，正如爱因斯坦所说，智慧的发现都是简单的。