Luogu

分析

首先对碱基序列建出 SAM 。

那么只需要在 SAM 上爆搜即可。具体的，每次枚举下一位，如果相同就直接过去，如果不同就改一次再过去。

注意清空。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,ans,id[256];
char s[N];

int lst,cnt;
int fa[N],len[N],sz[N],ch[N][4];
int o[N],a[N];

inline int newnode() {
    ++cnt,fa[cnt]=len[cnt]=sz[cnt]=0;
    memset(ch[cnt],0,sizeof(ch[cnt]));
    return cnt;
}

inline void extend(int c) {
    int p=lst,np=newnode(); lst=np,len[np]=len[p]+1,sz[np]=1;
    for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if (!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if (len[p]+1==len[q]) fa[np]=q;
        else {
            int nq=newnode(); len[nq]=len[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q],fa[q]=fa[np]=nq;
            for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
}

inline void calc() {
    memset(o,0,sizeof(o));
    for (re int i=1;i<=cnt;++i) ++o[len[i]];
    for (re int i=1;i<=cnt;++i) o[i]+=o[i-1];
    for (re int i=1;i<=cnt;++i) a[o[len[i]]--]=i;
    for (re int i=cnt;i>1;--i) sz[fa[a[i]]]+=sz[a[i]];
}

inline void dfs(int u,int l,int c) {
    if (l>n) { ans+=sz[u]; return; }
    for (re int i=0;i<4;++i) {
        if (!ch[u][i]) continue;
        if (id[s[l]]==i) dfs(ch[u][i],l+1,c);
        else if (c<3) dfs(ch[u][i],l+1,c+1);
    }
}

int main() {
    id['A']=0,id['G']=1,id['C']=2,id['T']=3;
    int T=read();
    while (T--) {
        lst=cnt=1,ans=0; fa[1]=len[1]=sz[1]=0;
        memset(ch[1],0,sizeof(ch[1]));
        scanf("%s",s+1),n=strlen(s+1);
        for (re int i=1;i<=n;++i) extend(id[s[i]]);
        calc();
        scanf("%s",s+1),n=strlen(s+1);
        dfs(1,1,0); printf("%d\n",ans);
    }
    return 0;
}