P3805 【模板】manacher算法

 1 #include <bits/stdc++.h>
 2 #define up(i,l,r) for(register int i = (l);i <= (r); i++)
 3 #define dn(i,l,r) for(register int i = (l);i >= (r); i--)
 4 #define ll long long
 5 using namespace std;
 6 
 7 const int N = 21000000;
 8 int len,ans,r[N<<1];
 9 char s[N],str[N<<1];
10 
11 void init(){
12     len = strlen(s+1);
13     int k = -1;
14     str[++k] = ‘$‘;
15     up(i,1,len){
16         str[++k] = ‘#‘;
17         str[++k] = s[i];
18     }
19     str[++k] = ‘#‘;
20     len = k;
21 }
22 
23 void Manacher(){
24     init();
25     int id = 1,mx = 1;
26     up(i,1,len-1){
27         if(mx > i) r[i] = min(r[id*2-i],mx-i);
28         else r[i] = 1;
29         while(str[i+r[i]] == str[i-r[i]]) ++r[i];
30         if(i+r[i] > mx){
31             mx = i+r[i];
32             id = i;
33             ans = max(ans,r[i]);
34         }
35     }
36     printf("%d",ans-1);
37 }
38 
39 int main(){
40     scanf("%s",s+1);
41     Manacher();
42     return 0;
43 }