为什么没人用(SAM)啊
我们先把原来的模式串建一遍(SAM)，之后我们就可以求出(SAM)上每一个节点的(|endpos|)就可以知道每一个子串出现的次数了，也就是在模式串上的匹配数了
之后我们设(dp[i][j])表示前(i)个里组合出的子串在(SAM)上匹配到了(j)位置的方案数是多少，转移的时候就枚举每一个子串以及(SAM)上的每一个节点之后跑匹配就好了
最后的答案就是
[sum_{i=1}^{cnt}dp[m][i] imes sz[i]
]
之后第一维甚至可以直接滚动掉
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100005
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int mod=1e9+7;
struct E{int v,nxt;}e[maxn<<1];
int fa[maxn<<1],son[maxn<<1][26],len[maxn<<1],head[maxn<<1],sz[maxn<<1];
char S[maxn];
int dp[2][maxn<<1];
int n,m,num,cnt=1,lst=1,ans,o;
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 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<26;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
inline int find(int now) {for(re int i=1;i<=n;i++) {now=son[now][S[i]-'A'];if(!now) break;}return now;}
int main()
{
scanf("%d",&m);scanf("%s",S+1);n=strlen(S+1);
for(re int i=1;i<=n;i++) ins(S[i]-'A');
for(re int i=2;i<=cnt;i++) add(fa[i],i);dfs(1);
dp[0][1]=1; o=0;
for(re int i=1;i<=m;i++)
{
int T; o^=1; scanf("%d",&T);
for(re int j=1;j<=cnt;j++) dp[o][j]=0;
for(re int j=1;j<=T;j++)
{
scanf("%s",S+1);n=strlen(S+1);
for(re int k=1;k<=cnt;k++)
if(dp[o^1][k]) {int v=find(k);if(v) dp[o][v]=(dp[o][v]+dp[o^1][k])%mod;}
}
}
for(re int i=2;i<=cnt;i++) ans=(ans+(LL)dp[o][i]*(LL)sz[i]%mod)%mod;
printf("%d
",ans);
return 0;
}