[LeetCode] Longest Palindromic Substring_综合

[Problem]
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

[Analysis]
可以使用后缀树做，但是总觉得杀鸡用牛刀了。其实完全可以不用后缀树，直接用例子说明方法吧。例如adefedc：

（1）最长奇回文串：从头到尾分解出前缀和相应的后缀（重叠前缀的最后一个字符），并从前缀的尾部开始，后缀的头部开始，一一对应比较
前缀     后缀      回文前缀回文长度
a        adefedc   a         1*2-1=1
ad       defedc    d       1*2-1=1
ade      efedc     e       1*2-1=1
adef     fedc      def    3*2-1=5
adefe    edc       e   1*2-1=1
adefed   dc        d    1*2-1=1
adefedc c         c       1*2-1=1

（2）最长偶回文串：从头到尾分解出前缀和相应的后缀（不重叠前缀的最后一个字符），并从前缀的尾部开始，后缀的头部开始，一一对应比较
前缀     后缀     回文前缀回文长度
a        defedc   ""        0
ad       efedc    ""        0
ade      fedc     ""        0
adef     edc      ""        0
adefe    dc       ""        0
adefed   c        ""        0

（3）比较最长奇回文和最长偶回文，取最长的。

[Solution]

class Solution {
      
public:
    // common subsequence from the end of the first string and the begin of the second string
    int commonLength(string prefix, string suffix){
      
        int len1 = prefix.length();
        int len2 = suffix.length();
        int i = len1-1;
        int j = 0;
        int length = 0;
        while(i >= 0 && j < len2){
      
            if(prefix[i] == suffix[j]){
      
                length++;
                i--;
                j++;
            }
            else{
      
                break;
            }
        }
        return length * 2;
    }
   
    // longest odd palindrome
    string longestOddPalindrome(string s){
      
        int len = s.length();
        string longest = "";
        for(int i = 0; i < len; ++i){
      
            string prefix = s.substr(0, i+1);
            string suffix = s.substr(i, len-i);
            int commonLen = commonLength(prefix, suffix) - 1;
            if(commonLen > longest.length()){
      
                longest = s.substr(i - (commonLen+1)/2 + 1, commonLen);
            }
        }
        return longest;
    }
   
    // longest even palindrome
    string longestEvenPalindrome(string s){
      
        int len = s.length();
        string longest = "";
        for(int i = 0; i < len; ++i){
      
            string prefix = s.substr(0, i+1);
            string suffix = s.substr(i+1, len-i-1);
            int commonLen = commonLength(prefix, suffix);
            if(commonLen > longest.length()){
      
                longest = s.substr(i - commonLen/2 + 1, commonLen);
            }
        }
        return longest;
    }
   
    // longest palindrome
    string longestPalindrome(string s) {
      
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string odd = longestOddPalindrome(s);
        string even = longestEvenPalindrome(s);
        return odd.length() > even.length() ? odd : even;
    }
};