标签 字符串 下的文章

「Luogu 4173」残缺的字符串

题目链接：Luogu 4173

很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串 $A$ 和 $B$，其中 $A$ 串长度为 $m$，$B$ 串长度为 $n$。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。

你想对这两个串重新进行匹配，其中 $A$ 为模板串，那么现在问题来了，请回答，对于 $B$ 的每一个位置 $i$，从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配？

数据范围：$1 \le m \le n \le 3 \times 10 ^ {5}$。

「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}$。

「NOI 2015」品酒大会

题目链接：UOJ 131

一年一度的「幻影阁夏日品酒大会」隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发「首席品酒家」和「首席猎手」两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 $n​$ 杯鸡尾酒。这 $n​$ 杯鸡尾酒排成一行，其中第 $i​$ 杯酒 （$1 \le i \le n​$） 被贴上了一个标签 $s_i​$，每个标签都是 $26​$ 个小写英文字母之一。设 $\text{Str}(l, r)​$ 表示第 $l​$ 杯酒到第 $r​$ 杯酒的 $r − l + 1​$ 个标签顺次连接构成的字符串。若 $\text{Str}(p, p_0) = \text{Str}(q, q_0)​$，其中 $1 \le p \le p_0 \le n​$，$1 \le q \le q_0 \le n​$，$p \ne q​$，$p_0 − p + 1 = q_0 − q + 1 = r​$，则称第 $p​$ 杯酒与第 $q​$ 杯酒是「$r​$ 相似」的。当然两杯「$r​$ 相似」（$r > 1​$）的酒同时也是「$1​$ 相似」、「$2​$ 相似」、$\dots​$、「$(r − 1)​$ 相似」的。特别地，对于任意的 $1 \le p, q \le n​$，$p \ne q​$，第 $p​$ 杯酒和第 $q​$ 杯酒都是「$0​$ 相似」的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了「首席品酒家」的称号，其中第 $i$ 杯酒 （$1 \le i \le n$） 的美味度为 $a_i$。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 $p$ 杯酒与第 $q$ 杯酒调兑在一起，将得到一杯美味度为 $a_p \cdot a_q$ 的酒。现在请各位品酒师分别对于 $r = 0, 1, 2, \dots, n − 1$，统计出有多少种方法可以选出两杯「$r$ 相似」的酒，并回答选择两杯「$r$ 相似」的酒调兑可以得到的美味度的最大值。

数据范围：$1 \le n \le 3 \times 10 ^ 5$，$\lvert a_i \rvert \le 10 ^ 9$。

「NOI 2016」优秀的拆分

题目链接：UOJ 219

如果一个字符串可以被拆分为 $\text{AABB}​$ 的形式，其中 $\text{A}​$ 和 $\text{B}​$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。

例如，对于字符串 $ \texttt{aabaabaa} ​$ ，如果令 $\text{A}=\texttt{aab}​$，$\text{B}=\texttt{a}​$，我们就找到了这个字符串拆分成 $\text{AABB}​$ 的一种方式。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。

比如我们令 $\text{A}=\texttt{a}$，$\text{B}=\texttt{baa}$，也可以用 $\text{AABB}$ 表示出上述字符串；但是，字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

1. 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
2. 在一个拆分中，允许出现 $\text{A}=\text{B}​$。例如 $\texttt{cccc}​$ 存在拆分 $\text{A}=\text{B}=\texttt{c}​$。
3. 字符串本身也是它的一个子串。

本题有 $T​$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n \le 3 \times 10 ^ 4$。

「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$。

「Codeforces 432D」Prefixes and Suffixes

题目链接：Codeforces 432D

你有一个字符串 $S$，你需要求出所有匹配的前后缀，并计算出这些前后缀在字符串中出现的次数。

数据范围：$1 \le \lvert S \rvert \le 10 ^ 5$。

「Codeforces 633C」Spy Syndrome 2

题目链接：Codeforces 633C

Yash 研究出了一种新的密码技术。对于给定的句子，密码通过以下方法生成：

1. 将所有字母都变成小写。
2. 将每个单词分别反转。
3. 将句子里的空格全部删除。

现在 Yash 给你一个长度为 $n$ 的加密后的句子 $S$ 和一个长度为 $m$ 的单词列表 $w_i$。请你帮助他找出任何一种可能的原始句子，使得句子里的单词都来自于单词列表。注意：任何给定的单词都可以多次使用。

数据范围：$1 \le \lvert S \rvert \le 10 ^ 4$，$1 \le m \le 10 ^ 5$，$1 \le \lvert w_i \rvert \le 10 ^ 3$，$\sum \lvert w_i \rvert \le 10 ^ 6$。

「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$。

「USACO 2015 Feb. Gold 2」Censoring

题目链接：USACO 2015 Feb. Gold 2

有一个字符串 $S$。Farmer John 希望在 $S$ 中删掉 $n$ 个屏蔽词（一个屏蔽词可能出现多次），这些词记为 $t_1 \sim t_n$。

FJ 在 $S$ 中从头开始寻找屏蔽词，一旦找到一个屏蔽词，FJ 就删除它，然后又从头开始寻找（而不是接着往下找）。FJ 会重复这一过程，直到 $S$ 中没有屏蔽词为止。注意删除一个单词后可能会导致 $S$ 中出现另一个屏蔽词。这 $n$ 个屏蔽词不会出现一个单词是另一个单词子串的情况，这意味着每个屏蔽词在 $S$ 中出现的开始位置是互不相同的，请帮助 FJ 完成这些操作并输出最后的 $S$。

数据范围：$1 \le \lvert S \rvert, \sum\lvert t_i \rvert \le 10 ^ 5$。

「Codeforces 1073G」Yet Another LCP Problem

题目链接：Codeforces 1073G

定义 $\text{LCP}(s, t)$ 字符串 $s$ 和 $t$ 的最长公共前缀，再定义 $s[x\dots y]$ 为字符串 $s$ 从位置 $x$ 到 $y$ 的子串。

给定一个长度为 $n$ 的字符串 $s$ 和 $q$ 个询问。每次询问给出两个长度分别为 $k_i, l_i$ 的序列 $a, b$。你需要计算 $\sum_{i = 1} ^ k \sum_{j = 1} ^ l \text{LCP}(s[a_i \dots n], s[b_j \dots n])$ 的值。

数据范围：$1 \le n, q, \sum k_i, \sum l_i \le 2 \times 10 ^ 5$，$1 \le k_i, l_i \le n$。