1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
const int M = 11001000*2;
char str[M];
int p[M];
char s[M];
int n;
void checkmax(int &ans,int b){
    if(b>ans) ans=b;
}
inline int min(int a,int b){
    return a<b?a:b;
}
void kp(){
    int i;
    int mx = 0;
    int id;
    for(i=1; i<n; i++){
        if( mx > i )
            p[i] = min( p[2*id-i], p[id]+id-i );
        else
            p[i] = 1;
        for(; str[i+p[i]] == str[i-p[i]]; p[i]++) ;
        if( p[i] + i > mx ) {
            mx = p[i] + i;
            id = i;
        }
    }
}
void pre()
{
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX