/**
 * @file maxPalindrome.cpp
 * @date 2011/12/07 19:40:29
 * @version $Revision$ 
 * @brief 
 *  
 **/

#include "../common/inc.h"

/**
 * @brief
 *    在字符串str中找出最大回文子串
 *    通过参数pSubPal和subPalLen返回此子串在str的偏移，以及子串的长度
 * @return 0-sucess， else fail.
 *
 * @algorithm
 *        From hongcheng's blog
 *        http://zhuhongcheng.wordpress.com/2009/08/02/a-simple-linear-time-algorithm-for-finding-longest-palindrome-sub-string/?like=1&_wpnonce=6ca936a13a
 *
 *        Given a string S, we are to find the longest sub-string s of S such that the reverse of s is
 *        exactly the same as s.
 *        First insert a special character ‘#’ between each pair of adjacent characters of S, in
 *        front of S and at the back of S. After that, we only need to check palindrome sub-strings of
 *        odd length.
 *        Let P[i] be the largest integer d such that S[i-d,,i+d] is a palindrome.  We calculate
 *        all P[i]s from left to right. When calculating P[i], we have to compare S[i+1] with S[i-1],
 *        S[i+2] with S[i-2] and so on. A comparison is successful if two characters are the same,
 *        otherwise it is unsuccessful. In fact, we can possibly skip some unnecessary comparisons
 *        utilizing the previously calculated P[i]s.
 *        Assume P[a]+a=max{ P[j]+j :  j<i }. If P[a]+a >= i, then we have
 *        P[i] >= min{ P[2*a-i],  2*a-i-(a- P[a])}.
 *        Is it the algorithm linear time? The answer is yes.
 *        First the overall number of unsuccessful comparisons is obviously at most N.
 *        A more careful analysis show that S[i] would never be compared successfully with any
 *        S[j](j<i) after its first time successful comparison with some S[k] (k<i).
 *        So the number of overall comparisons is a most 2N.     
 *
 *
 * */
enum{
    MaxP = 1024*1024,
};
int p[MaxP];
char s[MaxP];
int n = 0;

char str[MaxP/2 - 10];

int pre(const char *str)
{
    n = 0;
    if (NULL == str) return -1;
    int i = 0;
    p[i] = 0;
    s[i++] = '\1';
    while (*str) {
        p[i] = 0;
        s[i++] = *str;
        p[i] = 0;
        s[i++] = '\1';
        ++str;
    }
    s[i++] = '\0';
    n = i;
    return 0;
}

int kp()
{
    int i = 0;
    int m = 0;
    int a = 0;
    for (i=1; i<n; ++i) {
        if (m > i) {
            p[i] = min(p[2*a-i], p[a]+a-i);
        } else {
            p[i] = 1;
        }
        for (; i>=p[i] && s[i+p[i]] != '\0' && s[i+p[i]] == s[i-p[i]]; p[i]++);
        if (p[i]+i > m) {
            m = p[i]+i;
            a = i;
        }
    }
    return 0;
}

int out()
{
    int m = 0;
    int o = 0;
    for (int i=0; i<n; ++i) {
        if (p[i] > m) {
            o = i;
            m = p[i];
        }
    }
    char ch = s[0];
    o = (o -m + 1)/2;
    if (ch == '\1') m--;
    str[o+m] = 0;    
    printf("off:%d, len:%d, palindrome:%s\n\n", o, m, str + o);

}

int maxPalindrome(const char * str)
{
    if (NULL == str) return -1;
    pre(str);
    kp();
    out();
    return 0;
}

int main(int argc, char ** argv)
{
    printf("input the string, while given the max palindrome.\n");
    printf("string: ");
    while (EOF != scanf("%s", str)) {
        maxPalindrome(str);
        printf("string: ");
    }
    return 0;
}











/* vim: set ts=4 sw=4 sts=4 tw=100 noet: */