01.06.md

最长回文子串的长度

题目描述

给定一个字符串，求它的最长回文子串的长度。

分析与解法

最容易想到的办法是枚举所有的子串，分别判断其是否为回文。这个思路初看起来是正确的，但却做了很多无用功，如果一个长的子串包含另一个短一些的子串，那么对子串的回文判断其实是不需要的。

解法一

那么如何高效的进行判断呢？借鉴KMP算法的做法，既然对短的子串的判断和包含它的长的子串的判断重复了，我们何不复用下短的子串的判断呢，即让短的子串的判断成为长的子串的判断的一个部分。

没错，扩展法。从一个字符开始，向两边扩展，看看最多能到多长，使其保持为回文。这也就是为什么我们在上一节里面要提出解法二的原因。

具体而言，我们可以枚举中心位置，然后再在该位置上用扩展法，记录并更新得到的最长的回文长度，即为所求。代码如下：

/**  
 *find the longest palindrome in a string, n is the length of string s 
 *Copyright(C) fairywell 2011 
 */  
int LongestPalindrome(const char *s, int n)  
{
    int i, j, max;  
    if (s == 0 || n < 1) return 0;  
    max = 0;  
    for (i = 0; i < n; ++i) { // i is the middle point of the palindrome  
        for (j = 0; (i-j >= 0) && (i+j < n); ++j) // if the lengthof the palindrome is odd  
            if (s[i-j] != s[i+j]) 
              break;  
        if (j*2+1 > max) 
          max = j * 2 + 1;  
        for (j = 0; (i-j >= 0) && (i+j+1 < n); ++j) // for theeven case  
            if (s[i-j] != s[i+j+1]) 
              break;  
        if (j*2+2 > max) 
          max = j * 2 + 2;  
    }  
    return max;  
}  

代码稍微难懂一点的地方就是内层的两个 for 循环，它们分别对于以 i 为中心的，长度为奇数和偶数的两种情况，整个代码遍历中心位置 i 并以之扩展，找出最长的回文。

当然，还有更先进但也更复杂的方法，比如用 s 和逆置 s' 的组合 s$s' 来建立后缀树的方法也能找到最长回文，但构建的过程比较复杂，所以在实践中用的比较少，感兴趣的朋友可以参考相应资料。--well。

解法二、O(N)解法

参考：http://bbs.dlut.edu.cn/bbstcon.php?board=Competition&gid=23474 ，或这篇文章：http://www.felix021.com/blog/read.php?2040 ，或：http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html ，待续。