标签 后缀自动机 下的文章

「2019 Multi-University Training Contest 1」Typewriter

题目链接：HDU 6583

有一天，Jerry 发现了一个奇怪的打字机。这个打字机又 $2$ 种模式：第一种模式可以花费 $p$ 的代价在最后插入一个任意字符；第二种模式可以花费 $q$ 的代价复制任意一个子串并插在最后。

现在 Jerry 想要给 Tom 写一封信，这封信可以用一个只包含小写字母的字符串 $S$ 表示。可惜 Jerry 很穷所以他想知道写这封信的最小花费。

本题由多组数据。

数据范围：$1 \le \lvert S \rvert \le 2 \times 10 ^ {5}$，$\sum \lvert S \rvert \le 5 \times 10 ^ {6}$。

「CTSC 2012」熟悉的文章

题目链接：Luogu 4022

阿米巴是小强的好朋友。

在小强眼中，阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛，小强向阿米巴求教。阿米巴给小强展示了几篇作文，小强觉得这些文章怎么看怎么觉得熟悉，仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光，却发现阿米巴露出了一个狡黠的微笑。

为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得眼熟，小强想出了一个评定作文「熟悉程度」的量化指标：$L_0$。小强首先将作文转化成一个 $01$ 串。之后，小强搜集了各路名家的文章，同样分别转化成 $01$ 串后，整理出一个包含了 $m$ 个 $01$ 串的标准作文库。

小强认为：如果一个 $01$ 串长度不少于 $L$ 且在标准作文库中的某个串里出现过（即它是标准作文库 的某个串的一个连续子串），那么它是「熟悉」的。对于一篇作文 $A$，如果能够把 $A$ 分割成若干段子串，其中「熟悉」的子串的长度总和不少于 $A$ 总长度的 $90\%$，那么称 $A$ 是「熟悉的文章」。$L_0$ 是能够让 $A$ 成为「熟悉的文章」的所有 $L$ 的最大值。如果不存在这样的 $L$，那么规定 $L_0 = 0$。

现在小强有 $n$ 篇作文需要进行判断，请你分别求出他们的 $L_0$ 值。

数据范围：输入文件的长度不超过 $1.1 \times 10 ^ 6​$ 字节。

「NOI 2018」你的名字

题目链接：UOJ 395

小 A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。

由于 ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。

由于一些特殊的原因，小 A 不知道 ION2017 每道题的名字，但是他通过一些特殊手段得到了 ION2017 的命名串，现在小 A 有 $Q$ 次询问：每次给定 ION2017 的命名串 $S$ 和 ION2018 的命名串 $T$，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。

由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串 $S[l \dots r]$。

数据范围：$1 \le \lvert S \rvert \le 5 \times 10 ^ 5$，$1 \le Q \le 10 ^ 5$，$\sum \lvert T \rvert \le 10 ^ 6$，$1 \le l \le r \le \lvert S \rvert$。

「SDOI 2016」生成魔咒

题目链接：LOJ 2033

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 $1$、$2$ 拼凑起来形成一个魔咒串 $[1, 2]$。

一个魔咒串 $S$ 的非空子串被称为魔咒串 $S$ 的生成魔咒。

例如 $S = [1, 2, 1]$ 时，它的生成魔咒有 $[1]$、$[2]$、$[1, 2]$、$[2, 1]$、$[1, 2, 1]$ 五种。$S = [1, 1, 1]$ 时，它的生成魔咒有 $[1]$、$[1, 1]$、$[1, 1, 1]$ 三种。

最初 $S$ 为空串。共进行 $n$ 次操作，每次操作是在 $S$ 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 $S$ 共有多少种生成魔咒。

数据范围：$1 \le n \le 10 ^ 5$，$1 \le \Sigma \le 10 ^ 9$。

「Codeforces 700E」Cool Slogans

题目链接：Codeforces 700E

Bomboslav 成立了一个品牌代理商，正在帮助公司创建商标和广告。就这个问题而言，公司的广告应该是其名称的非空子串。

有时，公司会对品牌进行重塑并改变广告。如果广告 $B$ 作为子串在广告 $A$ 中出现至少 $2$ 次（允许重叠），那么认为广告 $A$ 比 $B$ 更酷。

你得到了某个公司的名字 $w$，你的任务是帮助 Bomboslav 确定最长的广告序列 $s_1, s_2, \dots, s_k$ 满足任何一个广告都比上一个更酷。

数据范围：$1 \le \lvert w \rvert \le 2 \times 10 ^ 5$。