5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

根据分而治之的思想，我试图寻找一种解决方案。以baba为例。欲求最大回文子串，我们先来看看回文字串，回文字串的出现分为两种情况，一种为在bab之内,另一种为包含最后一个字符a,
试问你还能找出其他的情况吗，不能。在bab之内的最大回文子串和包含a的最大回文字串再进行比较，就可以得到整个的字符串baba的最大回文子串。
在bab内的最大回文子串即子问题bab内的最大回文子串。我们抽象出下列公式。

f（s0,...,si) = max {f(s0,...,si-1),包含si的最大回文子串}
根据这一公式，实现程序如下。

bool check(char *s, int index1, int index2) {
    while(index2>index1){
        if(s[index1] != s[index2]) return false;
        index1++;
        index2--;
    }
    return true;
}

int incluLast(char *s, int last, int *index){
    *index = last;
    int common = 1;
    for(int i=0; i<last; i++) {
        if(check(s, i, last))
            if(last-i+1>common){
                common = last-i+1;
                *index = i;
                break;
            }
                
    }
    return common;
}


char* longestPalindrome(char* s) {
    int len = strlen(s);
    int compare;
    
    int index1=0, index2=0;
    int common = 1;
    
    for(int i=1; i<len; i++) {
        int tmp;
        compare = incluLast(s, i, &tmp);
        if(compare > common) {
            common = compare; index1=tmp; index2=i;
        }
    }
    
    s[index2+1] = '';
    return &s[index1];
}