palin

/*
 * Finding maximum length palindrom
 * Algorithm: Manacher
 * Order : linear O(n)
 */
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 1000007
char Str[MAX+7];
long N;             // N strlen
long Odd[MAX+7];    // Odd[i]  means max length palin centered i , total length 2*Odd[i]+1
long Even[MAX+7];   // Even[i] means max length palin centered i-1,i , total length 2*Even[i]
void Func( void )
{
    long i,k,L = 0,R = -1;
    for( i=0;i<N;i++ ){
        if( i>R ) k = 1;
        else k = min( Odd[L+R-i],R-i ) + 1;
        while( i+k<N && i-k>=0 && Str[i-k]==Str[i+k] ){
            k++;
        }
        Odd[i] = --k;
        if( i+k > R ){
            L = i-k;
            R = i+k;
        }
    }
    L = 0,R = -1;
    Even[0] = 0;
    for( i=1;i<N;i++ ){
        if( i>R ) k = 1;
        else k = min( Even[L+R-i+1],R-i+1 ) + 1;
        while( i+k-1<N && i-k>=0 && Str[i-k]==Str[i+k-1] ){
            k++;
        }
        Even[i] = --k;
        if( i+k-1 > R ){
            L = i-k;
            R = i+k-1;
        }
    }
}
int main( void )
{
    Func();
    return 0;
}