考虑只有一个串的如何处理
显然直接后缀自动机统计不同的子串个数
考虑多个串分别构建后缀自动机
那么对于一个可能的合法子串，它在自动机上的匹配一定是先在第一个自动机的根节点开始一直跑，只有当前自动机没有转移边了，那就跑到下一个自动机继续转移
为了尽可能地匹配所以只有当前自动机没有转移边了，才跑到下一个自动机
然后把所有子串分别构建一个后缀自动机，然后从后往前枚举一个个连起来，(原因代码有注释)
所有自动机构成了一个$DAG$，考虑在$DAG$上 $dfs$
如果要输出子串，开一个栈存当前子串，每 $dfs$ 到一个节点就输出栈内子串
如果只考虑统计数量则记 $f[i]$ 表示跑到节点 $i$ 以后的合法子串数量，跑记忆化搜索
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e7+7,mo=1e9+7; inline int fuck(char c)//把字符按字典序转成序号，请不要在意函数名... { if(c=='A') return 0; if(c=='C') return 1; return c=='G' ? 2 : 3; } inline char FUCK(int x)//把序号转成字符 { if(!x) return 'A'; if(x==1) return 'C'; return x==2 ? 'G' : 'T'; } //后缀自动机模板 int ch[N][4],fa[N],Max[N],tot,las,rt[N]; inline void ins(int c,int k) { int p=++tot,f=las; Max[las=p]=Max[f]+1; while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f]; if(!f) { fa[p]=rt[k]; return; } int v=ch[f][c]; if(Max[v]==Max[f]+1) { fa[p]=v; return; } int np=++tot; Max[np]=Max[f]+1; fa[np]=fa[v]; fa[v]=fa[p]=np; memcpy(ch[np],ch[v],sizeof(ch[np])); while(f&&ch[f][c]==v) ch[f][c]=np,f=fa[f]; } int n,k,cnt,f[N]; char s[N],st[N];//st存当前栈中字符 int Top; void dfs1(int x)//暴力枚举所以子串 { puts(st+1); ++cnt; for(int i=0;i<4;i++) { int &v=ch[x][i]; if(!v) continue; st[++Top]=FUCK(i); dfs1(v); st[Top--]=0; } } int dfs2(int x)//记忆化dfs统计方案 { if(f[x]) return f[x]; f[x]=1; for(int i=0;i<4;i++) { int &v=ch[x][i]; if(!v) continue; f[x]=(f[x]+dfs2(v))%mo; } return f[x]; } int main() { freopen("copy.in","r",stdin); freopen("copy.out","w",stdout); n=read(); for(int i=1;i<=n;i++) { las=rt[i]=++tot; scanf("%s",s+1); int len=strlen(s+1); for(int j=1;j<=len;j++) ins(fuck(s[j]),i); } for(int i=n;i;i--)//注意从后往前枚举 //因为自动机i缺少的转移边自动机i+1不一定有，可能在更后面的自动机有 //从后往前枚举可以保证 ch[rt[i+1]][k] 是后面所有自动机中第一个有 k 转移边的自动机 { for(int j=rt[i];j<rt[i+1];j++) for(int k=0;k<4;k++) if(!ch[j][k]) ch[j][k]=ch[rt[i+1]][k]; } k=read(); if(k) dfs1(rt[1]),printf("%d",cnt); else dfs2(rt[1]),printf("%d",f[rt[1]]); return 0; }