回文自动机求双倍回文
cpp
struct PAM{
static constexpr int ALPHABET_SIZE=26;
struct Node{
int len,link,cnt;// cnt表示以当前字符结尾的不同子串个数(视实际情况而定)
int trans;// 第一个长度小于等于一半的后缀
array<int,ALPHABET_SIZE> next;
};
vector<Node> t;
int suff;
string s;
PAM(){
init();
}
void init(){
t.assign(2,Node());//0为奇根，1为偶根
t[0].len=-1;
suff=1;
s.clear();
}
int newNode(){
t.emplace_back();
return t.size()-1;
}
bool add(int c){
int pos=s.size();
s+=c;
c=c-'a';
int cur=suff,curlen=0;
while(true){
curlen=t[cur].len;
if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos])break;
cur=t[cur].link;
}
if(t[cur].next[c]){
suff=t[cur].next[c];
return false;
}
suff=newNode();
t[suff].len=t[cur].len+2;
t[cur].next[c]=suff;
if(t[suff].len==1){
t[suff].link=1;
t[suff].trans=1;
return true;
}
if(t[suff].len<=2){
t[suff].trans=t[suff].link;
}
else{
int p=t[cur].trans;
while(t[p].len+2>t[suff].len/2||s[pos-1-t[p].len]!=s[pos])p=t[p].link;
t[suff].trans=t[p].next[c];
}
while(true){
cur=t[cur].link;
curlen=t[cur].len;
if(pos-1-curlen>=0&&s[pos-1-curlen]==s[pos]){
t[suff].link=t[cur].next[c];
break;
}
}
return true;
}
int next(int p,int c){
return t[p].next[c-'a'];
}
int link(int p){
return t[p].link;
}
int len(int p){
return t[p].len;
}
int cnt(int p){
return t[p].cnt;
}
int trans(int p){
return t[p].trans;
}
int size(){
return t.size();
}
} pam;
void solve(){
int n;
cin>>n;
string s;
cin>>s;
auto &t=pam.t;
for(int i=0;i<s.size();i++){
pam.add(s[i]);
}
int ans=0;
for(int i=2;i<t.size();i++){
if(pam.len(pam.trans(i))*2==pam.len(i)&&pam.len(i)%4==0)ans=max(ans,pam.len(i));
}
cout<<ans<<"\n";
}