2020-2021:teams:i_dont_know_png:nikkukun:palindrome_series
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:nikkukun:palindrome_series [2020/05/25 02:22] nikkukun 创建 |
2020-2021:teams:i_dont_know_png:nikkukun:palindrome_series [2020/08/07 18:11] (当前版本) nikkukun |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 首先不加证明地介绍一些 border 理论的引理，以便于之后集中使用。具体证明可以参考文末提及的资料，这里仅做记录。 | 首先不加证明地介绍一些 border 理论的引理，以便于之后集中使用。具体证明可以参考文末提及的资料，这里仅做记录。 | ||
| - | **引理 1（Weak Periodicity Lemma）** 若 $p, q \in \mathrm{per}(S)$，且 $p + q \leq |S|$，则 $\gcd(p, q) \in \mathrm{per}(S)$。 | + | > **引理 1（Weak Periodicity Lemma）** 若 $p, q \in \mathrm{per}(S)$，且 $p + q \leq |S|$，则 $\gcd(p, q) \in \mathrm{per}(S)$。 |
| - | **引理 2** 若 $p = \mathrm{minper}(S) \leq \dfrac {|S|}2$，则对任意 $x \in \mathrm{per}(S)$，有 $p \mid x$。 | + | > **引理 2** 若 $p = \mathrm{minper}(S) \leq \dfrac {|S|}2$，则对任意 $x \in \mathrm{per}(S)$，有 $p \mid x$。 |
| - | **引理 3** 串 $S$ 所有长度 $\geq \dfrac {|S|}2$ 的 border 长度构成一个等差数列。 | + | > **引理 3** 串 $S$ 所有长度 $\geq \dfrac {|S|}2$ 的 border 长度构成一个等差数列。 |
| 由引理 3 可以知道，串 $S$ 的 border 长度可以拆分为 $O(\log |S|)$ 段等差数列，只要不断对串 $S$ 中长度 $< \dfrac {|S|}2$ 部分的 border 递归使用引理 3 即可。 | 由引理 3 可以知道，串 $S$ 的 border 长度可以拆分为 $O(\log |S|)$ 段等差数列，只要不断对串 $S$ 中长度 $< \dfrac {|S|}2$ 部分的 border 递归使用引理 3 即可。 | ||
| 行 25: | 行 25: | ||
| 现在考虑回文树上 border 的情况。 | 现在考虑回文树上 border 的情况。 | ||
| - | **引理 4** 串 $S$ 的后缀 $T$ 是回文串，当且仅当 $T$ 为 $S$ 的 border。 | + | > **引理 4** 串 $S$ 的后缀 $T$ 是回文串，当且仅当 $T$ 为 $S$ 的 border。 |
| 这说明了对回文串的 border 都是回文串，同时再递归使用引理 3，可以发现一个回文串的 border 同样可以拆成 $O(\log |S|)$ 段等差数列，同时这些 border 还是回文串。 | 这说明了对回文串的 border 都是回文串，同时再递归使用引理 3，可以发现一个回文串的 border 同样可以拆成 $O(\log |S|)$ 段等差数列，同时这些 border 还是回文串。 | ||
| 行 37: | 行 37: | ||
| ===== 参考资料 ===== | ===== 参考资料 ===== | ||
| - | * 《子串周期查询问题的相关算法及其应用》- 陈孙立，国家集训队 2019 论文集 | + | - 《子串周期查询问题的相关算法及其应用》- 陈孙立，国家集训队 2019 论文集 |
| - | * [[https://zhuanlan.zhihu.com/p/92874690|字符串科技：Palindrome Series - Calabash]] | + | - [[https://zhuanlan.zhihu.com/p/92874690|字符串科技：Palindrome Series - Calabash]] |
| - | * [[https://www.cnblogs.com/yyf0309/p/9452065.html|Codeforces 932G Palindrome Partition - 阿波罗2003]] | + | - [[https://www.cnblogs.com/yyf0309/p/9452065.html|Codeforces 932G Palindrome Partition - 阿波罗2003]] |
2020-2021/teams/i_dont_know_png/nikkukun/palindrome_series.1590344531.txt.gz · 最后更改: 2020/05/25 02:22 由 nikkukun
