找到问题了。。。在下面代码的39行，典中典只删除修改过的数据以保证其严格线性
再加个关闭流同步优化一下子飙到总时长1s了，难绷
想着帮助以后的人就没删贴了
```
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,last,vcnt,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(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
string str;
cin>>t;
while(t--){
cin>>str;
n=str.size();
// memset(pam,0,sizeof(pam));
// memset(fail,0,sizeof(fail));
for(int i=0;i<=vcnt;i++)
memset(pam[i],0,sizeof(pam[i]));
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;
}
```
by MessageBoxA @ 2024-04-16 20:43:12