题解 | 【模板】最长回文串（Manacher）

#include <iostream>
using namespace std;
#include<string>
#include<algorithm>
#include<vector>
int main(){
int t;
cin>>t;
while(t--){

int op;
cin>>op;
int n;
cin>>n;
string s;
cin>>s;
s=' '+s;
string ss;
ss=' '+ss;
for(int i=1;i<=2*n+1;i++){
if(i%2==1){
    ss+='*';
}
else{
    ss+=s[i/2];
}

}
vector<int>v(2*n+3);
int ma=-1;
for(int i=1,r=1,c=1,len;i<=2*n+1;i++){
len=i<r?min(r-i,v[2*c-i]):1;
while(i-len>=1&&i+len<=2*n+1&&ss[i-len]==ss[i+len]){
    len++;
}

if(i+len>r){
    r=i+len;
    c=i;
}
v[i]=len-1;
ma=max(ma,v[i]);

}
if(op==1){
for(int i=1;i<=2*n+1;i++){
if(i%2==0){
    cout<<v[i]<<' ';
}


}
cout<<endl;

}
if(op==2){
for(int i=2;i<2*n+1;i++){
    if(i%2==1){
        cout<<v[i]<<' ';
    }
}
cout<<endl;

}

if(op==3){
long long sum=0;
for(int i=1;i<=2*n+1;i++){
    sum+=(v[i]+1)/2;
}

cout<<sum<<endl;


}

if(op==4){
int sum=0;
for(int i=1;i<=2*n+1;i++){

    if(v[i]==ma){
        sum++;
    }

}
cout<<sum<<endl;


}

}




    return 0;
}