NC200546 回文串

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 void manacher(string &ss, vector<int> &leftPart){
 5     vector<int> t(ss.size(),0);
 6     int middle=0;
 7     int rightBound=0;
 8     int len=ss.size();
 9      
10     for(int i=1;i<len;++i){
11         if(i<rightBound){
12             int left=middle-(i-middle);
13             t[i]=min(rightBound-i, t[left]);
14         }
15         while(i+t[i]<len && i-t[i]>=0 && ss[i+t[i]]==ss[i-t[i]]){
16             if(ss[i+t[i]]==‘#‘) leftPart[i+t[i]]=max(leftPart[i+t[i]],t[i]);
17             else leftPart[i+t[i]]=max(leftPart[i+t[i]],t[i]+1);
18              
19             ++t[i];
20         }
21         --t[i];
22         if(i+t[i]>rightBound){
23             rightBound=i+t[i];
24             middle=i;
25         }
26     }
27 }
28  
29 int main(){
30     string s;
31     cin>>s;
32     int N=s.size();
33     if(N<2) {
34         cout<<"0"<<endl;
35         return 0;
36     }
37      
38     int res=2;
39     string ss="";
40     for(int i=0;i<(int)s.size();++i){
41         ss+="#";
42         ss+=s[i];
43     }
44     ss+="#";
45     int M=ss.size();
46     vector<int> leftPart(M,0);
47     vector<int> rightPart(M,0);
48     for(int i=0;i<M;++i){
49         if(ss[i]==‘#‘){
50             leftPart[i]=0;
51             rightPart[i]=0;
52         }else{
53             leftPart[i]=1;
54             rightPart[i]=1;
55         }
56     }
57      
58     manacher(ss,leftPart);
59     string reverses="";
60     for(int i=M-1;i>=0;--i){
61         reverses+=ss[i];
62     }
63     manacher(reverses,rightPart);
64     for(int i=1;i<M;i++){
65         leftPart[i]=max(leftPart[i],leftPart[i-1]);
66         rightPart[i]=max(rightPart[i],rightPart[i-1]);
67     }
68     for(int i=1;i<M-1;++i){
69         if(ss[i]==‘#‘)    res=max(res,leftPart[i]+rightPart[M-1-i]);
70     }
71     cout<<res<<endl;
72     return 0;
73 }