Loj#6071. 「2017 山东一轮集训 Day5」字符串

FxorG · 2021-07-08 16:15:03 · 个人记录

题目

由于loj被我们机房墙了，所以只能用手机看题和交题了。

好了，我用vjudge交了。

这题是真的妙！

只有1个串，那么就是这题，这题可以用parent tree或者DAG上dp做，但是多个串就很难利用parent tree了。

我们考虑用DAG，但是去重怎么办？

回想一个串，因为SAM的任意一条路径表示的字符串都不同所以就去重了。

但是假如现在有字符串A的子串：NULL，o，or，orz，字符串B的子串有:NULL，z。

那么orz+NULL=or+z，我们怎么去重呢？

那么我们不让or转移到z就好了。具体地，假如一个串能够在本串的SAM下继续匹配下去就继续，否则才转移到下一个SAM。

\text{Code}

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

#define N (int)(4e6+5)
#define int long long
#define mod 1000000007

using namespace std;

char s[N];
int fa[N],son[26][N],len[N],rt[N];
int n,m,las,tot;

int ins(int c,int root) {
    if(son[c][las]) {
        int pre=las,y=son[c][pre];
        if(len[pre]+1==len[y]) return y;
        int x=++tot; len[x]=len[pre]+1;
        fa[x]=fa[y]; fa[y]=x;
        for(int i=0;i<26;i++) son[i][x]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=x;
        return x;
    }
    int pre=las,x=++tot; len[x]=len[pre]+1;
    for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
    int y=son[c][pre];
    if(!pre) fa[x]=root;
    else if(len[pre]+1==len[y]) fa[x]=y;
    else {
        int p=++tot; len[p]=len[pre]+1;
        fa[p]=fa[y]; fa[x]=fa[y]=p;
        for(int i=0;i<26;i++) son[i][p]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p;
    }
    return x;
}

int f[N];
int dfs(int x) {
    if(f[x]) return f[x];
    f[x]=1;
    for(int i=0;i<26;i++)
        if(son[i][x]) f[x]=(f[x]+dfs(son[i][x]))%mod;
    return f[x];
}

signed main() {
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1); m=strlen(s+1);
        rt[i]=++tot; las=rt[i];
        for(int j=1;j<=m;j++) las=ins(s[j]-'a',rt[i]); 
    //  cout<<rt[i]<<" ";
    }
    for(int i=n-1;i>=1;i--) {  
        for(int j=rt[i];j<rt[i+1];j++) {
            for(int c=0;c<26;c++) {
                if(!son[c][j]) son[c][j]=son[c][rt[i+1]];   
            }
        }
    }
    printf("%lld",dfs(1));
    return 0;
}

/*

单串就SAM建DAG跑 ，DAG指G(V,son) 因为SAM的每一条路径表示的都是一个不同的子串

那么你就随便跑了 

对每个SAM建DAG，考虑能在本串SAM匹配下去就继续，不能才跳下一个SAM
保证去重

*/