[题目][https://www.lydsy.com/JudgeOnline/problem.php?id=4892]
好像用(SAM)做的都是(dfs)啊
其实这里也是搜索
如果用(SAM)来做非常好理解，就是从(SAM)上匹配这个字符串，允许有不超过三条转移边不一样
于是(dfs)做法非常显然了，就是爆搜这三条不一样的转移边在哪里，但是复杂度看起来好像很迷，可能是(inom{n}{3})也就是(O(n^3))级别
但是由于很多情况下选择某一条转移甚至都无法在(SAM)上有一个长度为(n)的匹配，所以(dfs)非常的快
这里写的是一个(bfs)，但是长得和(dp)有点像？
设(f[i][j][k])表示在(SAM)上跑了(i)位跑到了(j)这个节点，(k)次个位置不一样是否可行，显然的转移就是枚举下一个是走(A,C,G,T)
发现这个数组可以滚动，之后就滚动好了
滚动的同时还需要滚动两个栈，用来存储有用的状态，其实就是广搜里的队列了
还有一个小剪枝，我们提前处理出每一个节点往下跑出来的最长路，我们可以根据这个快速判断出一个状态是否可行
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 200005
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
int Test,lst,cnt,num,n,top[2],tot,o;
struct St {int a,b;} st[2][maxn];
struct E{int v,nxt;} e[maxn<<1];
char S[maxn>>1],T[maxn>>1];
int son[maxn][4],fa[maxn],sz[maxn],len[maxn],head[maxn],mx[maxn],q[maxn],r[maxn],f[maxn][4];
inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
void dfs(int x) {for(re int i=head[x];i;i=e[i].nxt) dfs(e[i].v),sz[x]+=sz[e[i].v];}
inline int solve(char c) {if(c=='A') return 0;if(c=='C') return 1;if(c=='G') return 2;return 3;}
inline void ins(int c)
{
int f=lst,p=++cnt; lst=p;
len[p]=len[f]+1,sz[p]=1;
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
int x=son[f][c];
if(len[f]+1==len[x]) {fa[p]=x;return;}
int y=++cnt;
len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;
for(re int i=0;i<4;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
int main()
{
scanf("%d",&Test);
while(Test--)
{
scanf("%s",S+1);scanf("%s",T+1);
for(re int i=1;i<=cnt;i++)
r[i]=head[i]=mx[i]=len[i]=fa[i]=sz[i]=son[i][0]=son[i][1]=son[i][2]=son[i][3]=0;
top[0]=top[1]=0;
lst=cnt=1,num=0;
n=strlen(S+1);
for(re int i=1;i<=n;i++) S[i]=solve(S[i]),ins(S[i]);
for(re int i=2;i<=cnt;i++) add(fa[i],i); dfs(1);
num=tot=o=0;
for(re int i=1;i<=cnt;i++) head[i]=0;
for(re int i=1;i<=cnt;i++)
for(re int j=0;j<4;j++) if(son[i][j]) add(son[i][j],i),r[i]++;
for(re int i=1;i<=cnt;i++) if(!r[i]) q[++tot]=i;
for(re int i=1;i<=tot;i++)
for(re int j=head[q[i]];j;j=e[j].nxt)
{r[e[j].v]--; mx[e[j].v]=max(mx[e[j].v],mx[q[i]]+1);if(!r[e[j].v]) q[++tot]=e[j].v;}
n=strlen(T+1);
for(re int i=1;i<=n;i++) T[i]=solve(T[i]);
memset(f,0,sizeof(f));
st[0][++top[0]]=(St){1,0};
for(re int i=1;i<=n;i++,o^=1)
{
for(re int j=1;j<=top[o];j++)
f[st[o][j].a][st[o][j].b]=0;
top[o^1]=0;
for(re int j=1;j<=top[o];j++)
{
int x=st[o][j].a,y=st[o][j].b;
for(re int k=0;k<4;k++)
if(son[x][k]&&k!=T[i]&&y<3)
{
if(mx[son[x][k]]+i<n) continue;
if(!f[son[x][k]][y+1]) st[o^1][++top[o^1]]=(St){son[x][k],y+1},f[son[x][k]][y+1]=1;
}
int k=T[i];
if(!son[x][k]||mx[son[x][k]]+i<n) continue;
if(!f[son[x][k]][y]) st[o^1][++top[o^1]]=(St){son[x][k],y},f[son[x][k]][y]=1;
}
}
int ans=0;
for(re int i=2;i<=cnt;i++) if(f[i][0]||f[i][1]||f[i][2]||f[i][3]) ans+=sz[i];
printf("%d
",ans);
}
return 0;
}