2020-2021:teams:intrepidsword:2020-nowcoder-multi-8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:intrepidsword:2020-nowcoder-multi-8 [2020/08/05 11:32] admin D. Disgusting Relationship |
2020-2021:teams:intrepidsword:2020-nowcoder-multi-8 [2020/08/05 11:45] (当前版本) admin H. Hard String Problem |
||
|---|---|---|---|
| 行 58: | 行 58: | ||
| 时间复杂度 $\mathcal{O}(p\sqrt{p}+T\log n)$。 | 时间复杂度 $\mathcal{O}(p\sqrt{p}+T\log n)$。 | ||
| + | |||
| + | ===== H. Hard String Problem ===== | ||
| + | |||
| + | **题目大意**：给你 $n$ 个串，但是每个串实际上是所给串的无限循环。求公共子串数量。 | ||
| + | |||
| + | **题解**：首先注意到，每个串可以简化为最小循环，并转换为最小表示。相同的串可以删除。如果此时只剩一个串了，那么自然有无限个串。否则，考虑最短的串 $s$ 和 $t$。如果它们有一个长度 $\ge|s|+|t|$ 的公共子串，根据弱周期引理，$\gcd(|s|,|t|)$ 也是它们的周期，那么假如 $|s|\neq|t|$，与最小循环矛盾；否则与 $s\neq t$ 矛盾。因此公共子串最长为 $|s|+|t|-1$。这时将每个串循环几遍，使得包括所有这么长的子串即可。容易发现，除 $s,t$ 外的串长度至多变为原来的 $3$ 倍，因而仍能保证总串长，变为了经典 SAM 题。 | ||
2020-2021/teams/intrepidsword/2020-nowcoder-multi-8.1596598347.txt.gz · 最后更改: 2020/08/05 11:32 由 admin
