用的是第一篇题解的PAM+DP的思路，其他点最慢也只跑了3s，第一个点跑了10s+，感觉不大可能是常数问题，是不是遇到边界情况被卡了，但是没有提供数据下载，求调谢谢qwq

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,last,vcnt=1,ans;
int s[MAXN],pam[MAXN][4],fail[MAXN],len[MAXN],f[MAXN],nxt[MAXN];
inline int getfail(int x,int cur){
    while(x!=1 && (cur-len[x]-1<0 || s[cur]!=s[cur-len[x]-1])) x=fail[x];
    return x;
}
inline void add(int ch,int ind){
    int fa=getfail(last,ind);
    if(!pam[fa][ch]){
        vcnt++;
        len[vcnt]=len[fa]+2;
        int fafail=getfail(fail[fa],ind);
        fail[vcnt]=pam[fafail][ch];
        pam[fa][ch]=vcnt;
        if(len[vcnt]<=2) nxt[vcnt]=fail[vcnt];
        else{
            int cur=nxt[fa];
            while(ind-len[cur]-1<0 || s[ind-len[cur]-1]!=s[ind] || (len[cur]+2)*2>len[vcnt]) cur=fail[cur];//len[cur]+2 > len[vcnt]/2
            nxt[vcnt]=pam[cur][ch];
        }
    }
    last=pam[fa][ch];
}
int main(){
    int t;
    string str;
    cin>>t;
    while(t--){
        cin>>str;
        n=str.size();

        memset(pam,0,sizeof(pam));
        memset(fail,0,sizeof(fail));
        fail[0]=1;fail[1]=1;
        len[0]=0;len[1]=-1;
        last=0;
        ans=n;
        vcnt=1;

        for(int i=0;i<n;i++){
            if(str[i]=='A') s[i]=0;
            else if(str[i]=='T') s[i]=1;
            else if(str[i]=='C') s[i]=2;
            else if(str[i]=='G') s[i]=3;
            add(s[i],i);
        }
        for(int i=2;i<=vcnt;i++) f[i]=len[i];
        queue<int>q;
        f[0]=1;q.push(0);
        while(!q.empty()){
            int cur=q.front();q.pop();
            for(int i=0;i<4;i++){
                if(!pam[cur][i]) continue;
                int v=pam[cur][i];
                f[v]=min(f[v],f[cur]+1);
                f[v]=min(f[v],f[nxt[v]]+(len[v]/2-len[nxt[v]])+1);
                ans=min(ans,f[v]+(n-len[v]));
                q.push(v);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}