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>
#include<iostream>
using namespace std;
#define MAXN 1000100
char s[MAXN], str[MAXN*2];
int len, p[MAXN*2];
void Manacher()
{
     int mx = 0;
     int id;
     for (int i = 1; i < len; ++i)
     {
         if (mx > i)
            p[i] = min(p[id*2-i], mx-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;
                  }
         }
     
     
     }
int main()
{
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX