「2017 山东一轮集训 Day5」字符串

时间:2023-03-10 06:15:26
「2017 山东一轮集训 Day5」字符串

题目

比较神仙的操作啊

首先先考虑一个串的做法,我们有两种:SA或SAM,其中SAM又有两种,拓扑图上的\(dp\)和\(parent\)上随便统计一下

显然这道题\(SA\)和\(parent\)树都不是很好搞啊,考虑求一下拓扑图上的路径总数

我们先对每一个串单独建一个\(SAM\),每一个\(SAM\)都得到了一张\(DAG\)

对于一个节点\(x\)如果发现这个节点没有代表某个字母\(c\)的转移边,我们就找到这个串之后的一个有\(c\)的串,让\(x\)向那一张\(DAG\)的起始节点\(c\)转移边指向的点连边

现在我们建出来的\(DAG\)就非常牛逼了,如果发现想走某一条转移边而没有办法走的时候,它会自动跳到下一个字符串上去,我们在这张\(DAG\)上求一下路径总数就是答案了

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=1e9+7;
const int maxn=3e6+5;
int cnt,lst,n,tot,ans;
char S[maxn>>1];
int son[maxn][26],fa[maxn],len[maxn],rt[maxn>>1],r[maxn],q[maxn],dp[maxn];
int st[26][maxn>>1],top[26],now[26],ed[maxn>>1];
inline void ins(int c,int o) {
int f=lst,p=++cnt;lst=p;
len[p]=len[f]+1;
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=rt[o];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];
}
int main() {
scanf("%d",&n);
for(re int i=1;i<=n;i++) {
scanf("%s",S+1);
ed[i-1]=cnt;rt[i]=++cnt;lst=cnt;
int len=strlen(S+1);
for(re int j=1;j<=len;j++)
ins(S[j]-'a',i);
}
ed[n]=cnt;
for(re int i=2;i<=n;i++)
for(re int j=0;j<26;j++)
if(son[rt[i]][j]) st[j][++top[j]]=i;
for(re int j=0;j<26;j++) now[j]=1;
for(re int i=1;i<n;i++) {
for(re int j=0;j<26;j++)
while(now[j]<=top[j]&&st[j][now[j]]<=i) now[j]++;
for(re int j=rt[i];j<=ed[i];j++)
for(re int k=0;k<26;k++)
if(!son[j][k]&&now[k]<=top[k])
son[j][k]=son[rt[st[k][now[k]]]][k];
}
for(re int i=1;i<=cnt;i++)
for(re int j=0;j<26;j++)
if(son[i][j]) r[son[i][j]]++;
for(re int i=1;i<=cnt;i++) if(!r[i]) q[++tot]=i;
dp[1]=1;
for(re int i=1;i<=tot;i++) {
int x=q[i];
for(re int j=0;j<26;j++) {
if(!son[x][j]) continue;
r[son[x][j]]--;
dp[son[x][j]]=(dp[son[x][j]]+dp[x])%mod;
if(!r[son[x][j]]) q[++tot]=son[x][j];
}
}
for(re int i=1;i<=cnt;i++) ans=(ans+dp[i])%mod;
printf("%d\n",ans);
return 0;
}