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<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define MAXN 2000010
using namespace std;
char str[MAXN],s[MAXN*2];
int N,P[MAXN];
void init()
{
    memset(P,0,sizeof(P));
    int L=strlen(str);
    s[0]='!';
    s[1]='#';
    for(int i=0;i<L;i++)
    {
        s[(i<<1)+2]=str[i];
        s[(i<<1)+3]='#';
    }
    s[(L << 1)+2]=0;
}
int PK()
{
    int id=0,mx=0,L=strlen(s),ret=0;
    for(int i=1;i < L ;i++)
    {
        if(mx>i)
            P[i]=min(P[2*id-i],P[id]+id-i);
        else
            P[i]=1;
        for(;s[i+P[i]]==s[i-P[i]];P[i]++);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX