Leetcode 之 Longest Palindrome

#include <cstdio>
#include <algorithm>

int MAX_SIZE = 100000;

int gen_odd_str(const char * str, char * odd_str) {
    int i = 0;
    for (i = 0; *str != 0 ; ++i, ++str) {
        odd_str[2 * i] = '#';
        odd_str[2 * i + 1] = *str;
    }
    odd_str[2 * i] = '#';
    odd_str[2 * i + 1] = 0;
    return 2 * i + 1;
}

char* longestPalindrome(char* str) {
    using std::max;
    using std::min;
    char odd_str[MAX_SIZE];
    int p[MAX_SIZE], id, i, j, size;
    size = gen_odd_str(str, odd_str); p[0] = 1; id = 0;
    for (i = 1; i < size; ++i) {
        p[i] = max(1, min(p[id] - i, 2 * id - i > -1 ? p[2 * id - i] : 0));
        for (j = i - 1; j > -1 && odd_str[j] == odd_str[2 * i - j]; --j) ++p[i];
        if (p[i] > p[id]) id = i;
    }
    str = str + (id - p[id] + 1) / 2;
    str[p[id] - 1] = 0;
    return str;
}

int main(){
    char str[MAX_SIZE];
    while (!feof(stdin)) {
        gets(str);
        printf("%s", longestPalindrome(str));
    }
}