标签 后缀数组 下的文章

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

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

「Codeforces 452E」Three Strings

题目链接：Codeforces 452E

你有三个字符串 $(s_1, s_2, s_3)​$。对于每个整数 $l(1 \le l \le \min(\vert s_1 \vert, \vert s_2 \vert, \vert s_3 \vert)​$，你需要求出有多少三元组 $(i_1, i_2, i_3)​$ 满足 $s_k[i_k \dots i_k + l - 1](k = 1, 2, 3)​$ 两两相等。答案对 $10 ^ 9 + 7​$ 取模。

数据范围：$3 \le \sum_{i = 1} ^ 3 \vert s_i \vert \le 3 \times 10 ^ 5$。

「Codeforces 204E」Little Elephant and Strings

题目链接：Codeforces 204E

小象非常喜欢字符串。他拥有 $n$ 个包含小写字母的字符串，第 $i$ 个字符串记为 $a_i$。对于每个字符串 $a_i(1 \le i \le n)$，小象想要求出二元组 $(l, r)$ 的对数，其中 $(l, r)$ 需要满足：$1 \le l \le r \le \lvert a_i \rvert$ 且子串 $a_i[l\dots r]$ 是至少 $k$ 个字符串的子串。

数据范围：$1 \le n, k \le 10 ^ 5$，$\sum_{i = 1} ^ n \lvert a_i \rvert \le 10 ^ 5$。

「Codeforces 271D」Good Substrings

题目链接：Codeforces 271D

你有一个包含小写字母的字符串 $S​$，有一些字母是好的，其余的是坏的。如果在 $S_l, S_{l + 1}, \cdots, S_r​$ 中有至多 $k​$ 个坏的字母，那么子串 $S_{l,r}​$ 是好的。

你需要找出 $S​$ 中本质不同的好的子串数量。两个子串 $S_{x, y}​$ 和 $S_{p, q}​$ 是不同的当且仅当 $S_{x, y} \ne S_{p, q}​$。

数据范围：$1 \le \lvert S \rvert \le 1500$，$0 \le k \le \lvert S \rvert$。

「SPOJ 220」Relevant Phrases of Annihilation

题目链接：SPOJ 220

你是 Byteland 的国王，你的特工刚刚截获了 $n$ 条敌方的加密信息 $s_i$。你请来的密码学家声称他只能解密文本中最重要的部分，这个文字片段在所有信息中至少出现 $2​$ 次且不相交。你需要求出这个文字片段的最长长度。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n \le 10$，$2 \le \lvert s_i \rvert \le 10 ^ 4$。

「POJ 3415」Common Substrings

题目链接：POJ 3415

字符串 $T$ 的子串定义为：

$$ T(i,k) = T_iT_{i + 1}\cdots T_{t + k - 1}, 1 \le i \le i + k - 1 \le \lvert T \rvert $$

给定两个字符串 $A, B$ 和一个整数 $K$，我们定义 $S$ 为三元组 $(i, j, k)$ 集合：

$$ S = \{(i, j, k) \mid k \ge K, A(i, k) = B(j, k)\} $$

你需要求出集合 $S$ 的大小 $\lvert S \rvert$。

数据范围：$1 \le \lvert A \rvert, \lvert B \rvert \le 10 ^ 5$，$1 \le K \le \min(\lvert A \rvert, \lvert B \rvert)$。

「POJ 3693」Maximum Repetition Substring

题目链接：POJ 3693

我们定义一个字符串的重复数为最大的数字 $R$ 满足这个字符串可以被分割为 $R$ 个相同的连续子字符串。

给定一个长度为 $n$ 的字符串，你需要找到它的重复数最大的子串。如果有多个答案，输出字典序最小的子串。

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

「POJ 3261」Milk Patterns

题目链接：POJ 3261

农夫 John 发现他的奶牛的产奶量每天都在变化。经过进一步调查，他发现：虽然他不能预知未来的产奶量，但是每天的产奶量有一些规律。

为了进行更严格的研究，他发明了一种复杂的分类方案。他记录下了 $n$ 天内的产奶数据，第 $i$ 个产奶量样本被记录为 $a_i$。他希望找到最长的样本模式，其重复次数至少为 $k$ 次，模式之间可以重叠。

数据范围：$1 \le n \le 2 \times 10 ^ 4$，$0 \le a_i \le 10 ^ 6$，$2 \le k \le n$。