2019福建省队集训day1T2原样输出（copy）

痛定思痛。 2022-01-11 01:59 192阅读 0赞

### 题目描述： ###

nealchen 是一只 copycat。 它会把输入按行读入，原封不动地复制到输出中去。 但是在一次更新以后，它的程序出了一些问题。 它没法输出换行符了。 并且，读入的时候，总会莫名其妙地随机漏掉开头和结尾的若干个字符，甚至整行 都会漏掉。 比如 orznight 可能会变成 rzni ，orz，h 或者空串。 现在你找到一份输入文件丢给 nealchen，你想知道它的输出可能有多少种情况，以 及每种情况分别是什么。 由于你找到的输入文件全部来自之前的福建省选，所以所有的输入文件每行只可 能包含 $A,C,G,T$  四种字符。

### 输入： ###

第一行一个正整数 $n$ ，表示（题面中）输入文件的行数。 接下来 $n$ 行，表示输入文件的内容。保证这 $n$ 行中每行的每个字符是  $A.C,G,T$  四种字符中的一种。 接下来一个整数 $k(0≤k≤1)$  ，具体含义详见输出格式。

### 输出： ###

若 $k=0$  ，你需要输出一行，表示输出的可能情况个数模 $10^\{9\}+7$  的结果。 若 $k=1$  ，你需要按照字典序从小到大输出所有可能的输出情况，一行一个字符 串，最后一行输出输出的可能情况个数模 $10^\{9\}+7$  的结果。

### 算法标签：后缀自动机 ###

### 思路： ###

考虑对于一个字符串，你要去判断他是否能由给的字符串生成，此时我们会去贪心的匹配。

所以考虑反着想，我们建出对于每个串分别建后缀自动机，考虑对于一个节点如果存在关于 $a$ 的边，那我们会贪心的匹配继续往下走，否则我们会在之后的第一个出现a的地方继续匹配。于是我们联通一条当前点连向之后第一个有 $a$ 的串的点，也就是某一个串的根节点的儿子上。

之后相当于一个有向图，可以dfs统计答案或者拓扑统计答案。

### 以下代码： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    #define il inline
    #define _(d) while(d(isdigit(ch=getchar())))
    using namespace std;
    const int N=2e6+5,p=1e9+7;
    char res[N],s[N];
    int n,rt[N],ch[N][4],fa[N],last,cur=1,d[N],cnt=1;
    int nxt[N][4],f[N],ans,lst[4];
    il int read(){
        int x,f=1;char ch;
        _(!)ch=='-'?f=-1:f;x=ch^48;
        _()x=(x<<1)+(x<<3)+(ch^48);
        return f*x;
    }
    il int Ci(char cc){
        if(cc=='A')return 0;
        if(cc=='C')return 1;
        if(cc=='G')return 2;
        if(cc=='T')return 3;
    }
    il char Co(int x){
        if(x==0)return 'A';
        if(x==1)return 'C';
        if(x==2)return 'G';
        if(x==3)return 'T';
    }
    il int mu(int x,int y){
        if(x+y>=p)return x+y-p;
        return x+y;
    }
    il void build(int c,int id,int rot){
        last=cur;cur=++cnt;d[cur]=id;
        int p=last;
        for(;p&&!ch[p][c];p=fa[p])ch[p][c]=cur;
        if(!p)fa[cur]=rot;
        else{
            int q=ch[p][c];
            if(d[q]==d[p]+1)fa[cur]=q;
            else{
                int nt=++cnt;d[nt]=d[p]+1;
                memcpy(ch[nt],ch[q],sizeof(ch[q]));
                fa[nt]=fa[q];fa[q]=fa[cur]=nt;
                for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;
            }
        }
    }
    il int dp1(int rot,int x){
        if(f[x])return f[x];
        f[x]=1;
        for(int i=0;i<4;i++){
            if(ch[x][i])f[x]=mu(f[x],dp1(rot,ch[x][i]));
            else if(nxt[rot][i])
                f[x]=mu(f[x],dp1(nxt[rot][i],ch[rt[nxt[rot][i]]][i]));
        }
        return f[x];
    }
    il void prin(int l){
        for(int i=1;i<=l;i++)putchar(res[i]);
        putchar('\n');
        ans++;
    }
    il void dp2(int rot,int x,int tot){
        prin(tot);
        for(int i=0;i<4;i++){
            res[tot+1]=Co(i);
            if(ch[x][i])dp2(rot,ch[x][i],tot+1);
            else if(nxt[rot][i])
                dp2(nxt[rot][i],ch[rt[nxt[rot][i]]][i],tot+1);
        }
    }
    int main()
    {
        freopen("copy.in","r",stdin);
        freopen("copy.out","w",stdout);
        n=read();
        for(int i=1;i<=n;i++){
            scanf(" %s",s+1);
            cur=rt[i]=++cnt;
            int l=strlen(s+1);
            for(int j=1;j<=l;j++)build(Ci(s[j]),j,rt[i]);
        }
        for(int i=0;i<4;i++)
            if(ch[rt[n]][i])lst[i]=ch[rt[n]][i];
        for(int i=n-1;i;i--){
            for(int j=0;j<4;j++){
                if(ch[rt[i+1]][j])nxt[i][j]=i+1;
                else nxt[i][j]=nxt[i+1][j];
            }
        }
        int op=read();
        if(!op){
            printf("%d\n",dp1(1,rt[1]));
        }
        else{
            dp2(1,rt[1],0);
            printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Jessie-/p/10382142.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220110/bba16bd219d34fab8f23d62330cb9fdc.png