YZOJ P4258 [FJWC2019]原样输出

YZOJ P4258 [FJWC2019]原样输出

时间限制:4000MS      内存限制:262144KB

出题人:E.Space        难度:\(7.0\)

  • 题目描述

它会把输入按行读入,原封不动地复制到输出中去。

但是在一次更新以后,它的程序出了一些问题。

它没法输出换行符了。

并且,读入的时候,总会莫名其妙地随机漏掉开头和结尾的若干个字符,甚至整行都会漏掉。

比如 orzxxxxx 可能会变成 rzxxorzx 或者空串。

现在你找到一份输入文件丢给它,你想知道它的输出可能有多少种情况,以及每种情况分别是什么。

由于你找到的输入文件全部来自之前的福建省选,所以所有的输入文件每行只可能包含 ACGT 四种字符。

  • 输入格式

第一行一个正整数 \(n\),表示(题面中)输入文件的行数。

接下来 \(n\) 行,表示输入文件的内容。保证这 \(n\) 行中每行的每个字符是 ACGT 四种字符中的一种。

接下来一个整数 \(k, (0 \leq k \leq 1)\),具体含义详见输出格式。

  • 输出格式

若 \(k=0\),你需要输出一行,表示输出的可能情况个数模 \(10^9+7\) 的结果。

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

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(100\%\) 的数据,保证输入文件大小不超过 \(1MB\) ,保证输出文件大小不超过 \(200MB\) 。

 

 

 


 

 

 

考虑后缀自动机,\(k=0\) 统计本质串的数量即可,\(k=1\) 时直接按照字典序爆搜。

关键是SAM怎么建。

要建立一个恰好能识别题目所有串的自动机,那么就是在每一个后缀自动机上没有某一字符出边的节点上,把该字符对应的出边连到最近的一个后缀自动机上。

这样贪心的匹配,自动机恰好能识别所有串。

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注