Processing math: 1%

分类： 后缀自动机（SAM）

YZOJ P4258 [FJWC2019]原样输出

YZOJ P4258 [FJWC2019]原样输出

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

出题人：E.Space        难度：7.0

  • 题目描述

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

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

它没法输出换行符了。

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

比如 orzxxxxx 可能会变成 rzxx、orz、x 或者空串。

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

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

  • 输入格式

第一行一个正整数 n，表示（题面中）输入文件的行数。

接下来 n 行，表示输入文件的内容。保证这 n 行中每行的每个字符是 A、C、G、T 四种字符中的一种。

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

  • 输出格式

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

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

  • 样例输入

…

YZOJ P3897 Sevenk Love Oimaster

YZOJ P3897 Sevenk Love Oimaster

时间限制：1000MS      内存限制：131072KB

难度：7.5

  • 题目描述

有 n 个大串和 q 个询问，每次给出一个字符串 s 询问在多少个大串中出现过。

  • 输入格式

输入的第一行有两个整数分别代表 n 和 q 。

接下来的 n 行，分别给出题中所述的 n个只包含小写字母的字符串。

再接下来的 q 行，每行给出一个询问只包含小写字母的字符串。

  • 输出格式

对于每一个询问，输出一行答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

n \leq 10000, q \leq 60000 。

原串总长度 \leq 100000 。

询问串总长度 \leq 360000 。

 

 

 

Source: BZOJ 2780 && SPOJ 8093…

YZOJ P3847 [2018省队集训]Ernd

YZOJ P3847 [2018省队集训]Ernd

时间限制：1000MS      内存限制：131072KB

难度：8.0

  • 题目描述

给定一个长度为 n 且仅包含小写英文字母的字符串 S。你有一个字符串 T，初始为空串。

你可以进行 n 次操作，每次操作你可以在 T 的前端或末尾加入一个任意字母。记第 i 次操作后 T 在 S 中的出现次数为 f_i，你需要最大化 ans=\sum\limits_i f_i 。

  • 输入格式

第一行一个正整数 n 。

第二行一个长度为 n 的字符串 S 。

  • 输出格式

一行一个整数，表示 ans 的最大值。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 100\% 的数据，1 \leq n \leq 2\times 10^5 。

 

 

 …

YZOJ P3939 [HAOI2016]找相同字符

YZOJ P3939 [HAOI2016]找相同字符

时间限制：1000MS      内存限制：262144K

难度：6.5

  • 题目描述

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。

两个方案不同当且仅当这两个子串中有一个位置不同。

  • 输入格式

两行，两个字符串 s_1, s_2，1 \leq \left|s_1\right|, \left|s_2\right|\leq 200000，字符串中只有小写字母。

  • 输出格式

输出一个整数表示答案

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 4566…

YZOJ P2242 [ZJOI 2015]Substring

YZOJ P2242 [ZJOI 2015]Substring

时间限制：1000MS      内存限制：524288KB

难度：8.0

  • 题目描述

给出一棵 n 个节点、叶子不超过 20 个的树，每个节点上有 0 到 c-1 的数字。

树上任意两点 A、B 间的有向路径 A \rightarrow B 形成了一个字符串（A \rightarrow B 和 B \rightarrow A 构成的串相反）。

求总共有多少个互不相同的字符串。

  • 输入格式

第一行两个数，n, c 。

第二行 n 个 0~c-1 间的数，表示每个节点的颜色。

接下来 n-1 行，每一行表示一条树边。

保证叶子个数不超过 20。

  • 输出格式

一个整数，表示不同的字符串数。

  • 样例输入

  • 样例输出

  • 数据规模与约定

1 \leq n \leq 10000, 1 \leq c \leq 10 。

 

 

 

Source: BZOJ 3926…