2020-2021:teams:farmer_john:2020牛客暑期多校第八场
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第八场 [2020/08/07 17:52] 2sozx [题解] |
2020-2021:teams:farmer_john:2020牛客暑期多校第八场 [2020/10/07 21:25] (当前版本) jjleo [比赛名称] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======比赛名称====== | + | ======2020牛客暑期多校第八场====== |
| [[https://ac.nowcoder.com/acm/contest/5673|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/5673|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 43: | 行 43: | ||
| 给出$n$个字符串，将每个字符串重复循环无限次，问得到的$n$个新字符串有多少个本质不同的公共子串，若有无限个输出$-1$。$(\sum|s_i| \le 3 \times 10^5)$ | 给出$n$个字符串，将每个字符串重复循环无限次，问得到的$n$个新字符串有多少个本质不同的公共子串，若有无限个输出$-1$。$(\sum|s_i| \le 3 \times 10^5)$ | ||
| ====题解==== | ====题解==== | ||
| + | 首先求出每个字符串的最小表示法（使用Lyndon分解，C++自带rotate()也可以很好实现循环移位），将每个字符串用其最短循环节表示（求出next数组，设$x$为最后一个位置的next数组值，字符串长度为$len$，若$(len-x)|len$则最小循环节长度为$len-x$，否则最小循环节长度为$len$），如果此时出现了$n$个相同的字符串，显然有无穷多个公共子串；否则由弱周期引理可以证明，对于两个字符串来说公共子串长度不超过长串的三倍，对于多个字符串来说，只需考虑最短串和其它串的公共子串的交即可。 | ||
| + | 具体来说，将除最短串外的串扩大到四倍，将最短串扩大到最长串的四倍，然后求这些字符串的公共子串数目即可。使用SAM来求过于繁琐还容易写锅，对于多串问题可以使用更为简便的广义SAM。只需将所有串插入广义SAM，然后对于每个串，将所有能到达的点标记，然后考虑所有标记数为$n$的节点即可。标记时只需按照字符串走一遍，每走到一个点不断跳link直到跳到的点已经被该点标记为止，这样每个字符串相当于标记了属于自己的SAM，而SAM节点数量是线性的，因此总复杂度为$O(n)$。 | ||
| =====I.===== | =====I.===== | ||
| **solved by Bazoka13** | **solved by Bazoka13** | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第八场.1596793956.txt.gz · 最后更改: 2020/08/07 17:52 由 2sozx
