A ABB 马拉车算法

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int inf = 0x3f3f3f3f;
 4 const int maxx = 3e6+10;
 5 char tmp[maxx];
 6 int len[maxx];
 7 int ans=inf;
 8 void Manacher(string s)
 9 {
10     tmp[0]=‘$‘;
11     tmp[1]=‘#‘;
12     int t=s.size();
13     for(int i=0;i<2*t+5;i++)len[i]=0;
14     for(int i=1;i<=t;i++){
15         tmp[2*i]=s[i-1];
16         tmp[2*i+1]=‘#‘;
17     }
18     tmp[2*t+2]=‘\0‘;
19     int mx=0;
20     int mid;
21     for(int i=1;tmp[i];i++){
22         if(i<mx)len[i]=min(len[2*mid-i],mx-i);
23         else len[i]=1;
24         while(tmp[i-len[i]]==tmp[i+len[i]])len[i]++;
25         if(len[i]+i>mx){
26             mx=len[i]+i;
27             mid=i;
28         }
29         int l=len[i]-1;
30         if(i%2==0){
31             l=(l-1)/2;
32             int p=i/2;
33             if(p+l==t){
34                 ans=min(ans,p-l-1);
35             }
36         }
37         else{
38             l=l/2;
39             int p=(i-1)/2,q=(i+1)/2;
40             if(q+l-1==t){
41                 ans=min(ans,p-l);
42             }
43         }
44     }
45 }
46 int main()
47 {
48     int n;
49     cin>>n;
50     string s;
51     cin>>s;
52     Manacher(s);
53     cout<<ans<<endl;
54     return 0;
55 }