寻找最长回文串长度的一个动态规划解法
今天某面试题，要在任意给定的字符串中，寻找最长回文串的长度。
注：回文串是指abc、abbc、aaabccc、aaaccc这种左右对称的字符串。
比如：abcaabbbaad字符串中，最长回文串的长度是7。
?
public class SynmetricalSearchTest extends TestCase {public void testAbnormal() {assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection(null));assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection("".toCharArray()));}public void testOdd() {assertEquals(5, SymmetricalSearch.getLongestSymmetricalSection("12321".toCharArray()));assertEquals(3, SymmetricalSearch.getLongestSymmetricalSection("121".toCharArray()));}public void testEven() {assertEquals(4, SymmetricalSearch.getLongestSymmetricalSection("1221".toCharArray()));assertEquals(6, SymmetricalSearch.getLongestSymmetricalSection("123321".toCharArray()));}public void testMixOdd() {assertEquals(5, SymmetricalSearch.getLongestSymmetricalSection("asf12321drf".toCharArray()));assertEquals(3, SymmetricalSearch.getLongestSymmetricalSection("121".toCharArray()));}public void testMixEven() {assertEquals(4, SymmetricalSearch.getLongestSymmetricalSection("6781221787".toCharArray()));assertEquals(6, SymmetricalSearch.getLongestSymmetricalSection("55512332144".toCharArray()));}public void testMixNone() {assertEquals(0, SymmetricalSearch.getLongestSymmetricalSection("6784".toCharArray()));}public void testNesting() {assertEquals(7, SymmetricalSearch.getLongestSymmetricalSection("3332333".toCharArray()));assertEquals(6, SymmetricalSearch.getLongestSymmetricalSection("af323323ed".toCharArray()));}}?
---------------------------------------------------------
2012-3-26 更新：
同事提点我，这个做法是有问题的，如果出现这样的字符串，比如：abcdba，这个做法会认为ab是最大子串，那就错了，因此，这个算法在每次发现疑似最大回文串时都要进行校验，当然，这样效率就低了不少。
网上比较多的相对比较简单的正确解法是后缀树解法，这里有一位高人的blog。
不过，小罗同学说，甚至可以把复杂度降到O(n)！太不可思议了是不是？据说这叫Manacher算法，看这里和这里。
?
文章系本人原创，转载请注明出处和作者
?