Good problem. 题意 题目链接 Monocarp 词典包含 $n$ 个单词，由 $12$ 个拉丁字母组成。单词编号从 $1$ 到 $n$ 。每个单词中的每一对相邻字符都是不同的。对于每个单词 $i$ ，Monocarp 也有一个整数 $c_i$ ，表示他使用这个单词的频率。 Monocarp 想要设计一个键盘，让他可以轻松地输入其中的一…

很涩的一个题。 题意 题目链接 假如我们有一个 AC 自动机，我们可以取出其中的点，字符边和 Fail 边，这样其就变成了一个有 $n$ 个点和 $2n-2$ 条边的有向图。现在给出你这样一个有向图，你需要找到其原始的 AC 自动机结构（包括 1. 找到根 2. 找到哪些边是 Trie 树边 3. 给所有的 Trie 树边分配一个字符，字符集大小不…

内容参考： 牛客竞赛字符串专题-calabash_boy 樱雪喵-广义后缀自动机（广义 SAM）学习笔记 KMP KMP 是一种用于两个字符串匹配的算法。其核心概念是 Border ，即一个字符串同长度的完全相同的前后缀（通常不含自身）。 KMP 的做法是先求出要匹配的字符串（短串）的所有前缀的最长 Border，然后在于长串进行匹配，并在无法匹配…

题目链接。 解析 考虑最终序列。由于序列较长，先考虑序列短小的情况，即长度为 $3$ 时。 对于一个长度为 $3$ 的序列 $S_{1,2,3}$，要使其不存在回文串，需要满足 $S_1\neq S_2,S_2\neq S_3,S_1\neq S_3$，你发现这三个字母必须是互不相同的，由于字符串仅由三种字母组成，最终序列的前三个字母一定是以下六种…

博客参考：CSDN 的 文章, enceladus, yybyyb, hyfhaha 的代码启示，皎月半洒花 的 博客, hyfhaha 的 博客。 前置知识 I - KMP字符串匹配 模版：Luogu3375。 我觉得这玩意儿比 trie 树难理解一点。 给定两个字符串 $s_1$ 和 $s_2$，我们需要求出 $s_2$ 在 $s_1$ 中所有…

题意 题目链接 询问是否：对于 $s$ 中每一个 $s_i$，都找的到一个包含它的 $s$ 的子序列（不是子串）与 $t$ 相同。 解析 首先我们考虑，必须要按顺序找到第一个子序列，否则一定是 No。 例如，若 $t=abcd$，$s$ 的前几项可以为 $aabbbcdd$，但是不能为 $acbcd$，因为第一个 $c$ 一定不满足。 找到之后，我…