算法：最大回文子串问题

自己在2014年12月面试某公司时被问过该问题。虽然当时，自己写出来了自认为效率比较高的算法，但是没有能按照面试官的要求，进行进一步的优化。后来网上搜索该问题，结果引申了一串其他的知识点，看来还是得深究啊！

解法一：暴力法

这种方法就不用多说了吧。这里我给出暴力法中，最优化的方案。

# coding:utf-8

''' 由于是要求最长的回文串，所以我们可以从最长的子串开始遍历。当找到一个回文串后，就可以直接返回
了。不用再遍历那些短的子串了。
对于字符串s, 假设串长度为N,判断过程如下：
1. 最长的子串就是本身，所以判断s是不是子串。假如不是，进行下一步：
2. 然后判断串长度为N - 1的子串是不是，即：s[:N - 1], s[1:]
3. 依次进行下一轮判断.直到找到个是回文串的子串。

'''
# 判断s的子串:"s[i], s[i+1]... s[j]"是否是回文的
def check(s, i, j):
    tmp = s[i:j + 1]
    #print tmp
    #return tmp == tmp.reverse()
    return tmp == tmp[::-1]

def LongestPalindrome(s):
    if not s:
        return "", 0
    lenth = len(s)
    diffLen = lenth - 1
    #maxPalindrome = ""
    while diffLen >= 0:
        i = 0
        j = diffLen
        while j < lenth:
             if check(s, i, j):
                return  s[i:j+1], diffLen + 1
             i += 1
             j += 1
        diffLen -= 1

解法二：中心扩展法O(n2)

这个算法思想其实很简单，就是对给定的字符串S，分别以该字符串S中的每一个字符 c 为中心，向两边扩展，记录下以字符 c 为中心的回文子串的长度。时间复杂度为O(n2)，空间复杂度仅为O(1)。
但有一点需要注意的是，回文的情况可能是 a b a，也可能是 a b b a。

// 分别向左右扩展，返回扩展后的字符串
string expand(string s, int left, int right) {
    int len = s.size();
    while (left>=0 && right<len && s[left] == s[right]) 
    {
        left--;
        right++;
    }
    return s.substr(left+1, right-left-1);
}

// 求最长回文子串
string longestPalindrome(string s) {
    int len = s.size();
    if(len<=1) return s;

    string longest;
    for (int i=0; i<len-1; i++) 
    {
        string p1 = expand(s, i, i);  // 奇数
        if (p1.size() > longest.size())
            longest = p1;

        string p2 = expand(s, i, i+1);  // 偶数
        if (p2.size() > longest.size())
            longest = p2;
    }
    return longest;
}

面试时个人能想到就是这两种方法。此外此题还有动态规划法，Manacher法，后缀树方法。其中动态规划法这里不予以介绍，可以参考相关后面列出的参考文献。另外的两节会另外单独介绍！

参考文献：

http://songlee24.github.io/2015/05/12/longest-palindromic-substring/