2020-2021:teams:farmer_john:week_14
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:week_14 [2020/08/07 18:10] jjleo [JJLeo] |
2020-2021:teams:farmer_john:week_14 [2020/08/07 18:10] (当前版本) jjleo [JJLeo] |
||
|---|---|---|---|
| 行 44: | 行 44: | ||
| * 具体来说，将除最短串外的串扩大到四倍，将最短串扩大到最长串的四倍，然后求这些字符串的公共子串数目即可。使用SAM来求过于繁琐还容易写锅，对于多串问题可以使用更为简便的广义SAM。只需将所有串插入广义SAM，然后对于每个串，将所有能到达的点标记，然后考虑所有标记数为$n$的节点即可。标记时只需按照字符串走一遍，每走到一个点不断跳link直到跳到的点已经被该点标记为止，这样每个字符串相当于标记了属于自己的SAM，而SAM节点数量是线性的，因此总复杂度为$O(n)$。 | * 具体来说，将除最短串外的串扩大到四倍，将最短串扩大到最长串的四倍，然后求这些字符串的公共子串数目即可。使用SAM来求过于繁琐还容易写锅，对于多串问题可以使用更为简便的广义SAM。只需将所有串插入广义SAM，然后对于每个串，将所有能到达的点标记，然后考虑所有标记数为$n$的节点即可。标记时只需按照字符串走一遍，每走到一个点不断跳link直到跳到的点已经被该点标记为止，这样每个字符串相当于标记了属于自己的SAM，而SAM节点数量是线性的，因此总复杂度为$O(n)$。 | ||
| - | * comment：如果不仅仅当作结论题，可以说是结合了多种字符串算法，非常综合。 | + | * comment：如果不当作结论题，可以说是结合了多种字符串基础算法，非常综合。 |
| =====题目===== | =====题目===== | ||
| * [[2020.8.2|每日亿题2020.8.2]] | * [[2020.8.2|每日亿题2020.8.2]] | ||
2020-2021/teams/farmer_john/week_14.1596795005.txt.gz · 最后更改: 2020/08/07 18:10 由 jjleo
