好像用SAM写的很少诶……
其实我一开始也没想到要用SAM的……主要是没有想到找的时候可以dfs……
首先建一个SAM，然后跑一遍dfs，枚举一下下一位，如果相同直接继续，否则就花费一次次数来改变它，保证改变次数小于等于3就行了
1 // luogu-judger-enable-o2 2 //minamoto 3 #include4 #include 5 #include 6 using namespace std; 7 const int N=1e6+5; 8 int cnt[N<<1],fa[N<<1],ch[N<<1][4],l[N<<1],last,tot; 9 char s[N];int c[N],a[N],ans,m,val[N];10 void ins(int c){11 int p=last,np=++tot;last=np,l[np]=l[p]+1,cnt[np]=1;12 for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;13 if(!p) fa[np]=1;14 else{15 int q=ch[p][c];16 if(l[q]==l[p]+1) fa[np]=q;17 else{18 int nq=++tot;l[nq]=l[p]+1;19 memcpy(ch[nq],ch[q],sizeof(ch[q]));20 fa[nq]=fa[q],fa[q]=fa[np]=nq;21 for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;22 }23 }24 }25 inline void calc(){26 memset(c,0,sizeof(c));27 for(int i=1;i<=tot;++i) ++c[l[i]];28 for(int i=1;i<=tot;++i) c[i]+=c[i-1];29 for(int i=1;i<=tot;++i) a[c[l[i]]--]=i;30 for(int i=tot,p;i;--i)31 p=a[i],cnt[fa[p]]+=cnt[p];32 }33 void dfs(int p,int len,int j){34 if(len>m) return (void)(ans+=cnt[p]);35 for(int i=0;i<4;++i){36 if(!ch[p][i]) continue;37 // val[s[len]]==i?dfs(ch[p][i],len+1,j):j<3?dfs(ch[p][i],len+1,j+1):(void)(1);38 if(val[s[len]]==i) dfs(ch[p][i],len+1,j);39 else if(j<3) dfs(ch[p][i],len+1,j+1);40 }41 }42 int main(){43 // freopen("testdata.in","r",stdin);44 val['T']=0,val['A']=1,val['C']=2,val['G']=3;45 int T;scanf("%d",&T);46 while(T--){47 memset(ch,0,sizeof(ch)),memset(cnt,0,sizeof(cnt));48 last=tot=1,ans=0;49 scanf("%s",s+1);int len=strlen(s+1);50 for(int i=1;i<=len;++i) ins(val[s[i]]);51 calc();52 scanf("%s",s+1),m=strlen(s+1);53 dfs(1,1,0);printf("%d\n",ans);54 }55 return 0;56 }