2020-2021:teams:legal_string:后缀数组_lgwza
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:后缀数组_lgwza [2020/07/24 16:11] lgwza |
2020-2021:teams:legal_string:后缀数组_lgwza [2020/07/24 16:17] (当前版本) lgwza [一些常数优化] |
||
|---|---|---|---|
| 行 43: | 行 43: | ||
| 参考代码： | 参考代码： | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <algorithm> | #include <algorithm> | ||
| 行 86: | 行 87: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ==== $O(n\log n)$ 做法 ==== | ==== $O(n\log n)$ 做法 ==== | ||
| 行 97: | 行 98: | ||
| 参考代码： | 参考代码： | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <algorithm> | #include <algorithm> | ||
| 行 147: | 行 149: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ==== 一些常数优化 ==== | ==== 一些常数优化 ==== | ||
| 行 158: | 行 161: | ||
| 实际上，像这样就可以了： | 实际上，像这样就可以了： | ||
| + | |||
| <code cpp> | <code cpp> | ||
| 行 183: | 行 187: | ||
| 参考代码： | 参考代码： | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <algorithm> | #include <algorithm> | ||
| 行 228: | 行 233: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ==== $O(n)$ 做法 ==== | ==== $O(n)$ 做法 ==== | ||
| 行 267: | 行 273: | ||
| 参考代码： | 参考代码： | ||
| + | <hidden> | ||
| <code cpp> | <code cpp> | ||
| #include <cctype> | #include <cctype> | ||
| 行 322: | 行 329: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| - | ## height 数组 | + | ===== height 数组 ===== |
| - | + | ==== LCP（最长公共前缀） ==== | |
| - | + | ||
| - | ### LCP（最长公共前缀） | + | |
| 两个字符串 $S$ 和 $T$ 的 LCP 就是最大的 $x$ ($x\le\min(|S|,|T|)$) 使得 $S_i=T_i(\forall1\le i\le x)$。 | 两个字符串 $S$ 和 $T$ 的 LCP 就是最大的 $x$ ($x\le\min(|S|,|T|)$) 使得 $S_i=T_i(\forall1\le i\le x)$。 | ||
| 行 333: | 行 339: | ||
| 下文中以 $lcp(i,j)$ 表示后缀 $i$ 和后缀 $j$ 的最长公共前缀（的长度）。 | 下文中以 $lcp(i,j)$ 表示后缀 $i$ 和后缀 $j$ 的最长公共前缀（的长度）。 | ||
| - | + | ==== height 数组的定义 ==== | |
| - | + | ||
| - | ### height 数组的定义 | + | |
| $height[i]=lcp(sa[i],sa[i-1])$，即第 $i$ 名的后缀与它前一名的后缀的最长公共前缀。 | $height[i]=lcp(sa[i],sa[i-1])$，即第 $i$ 名的后缀与它前一名的后缀的最长公共前缀。 | ||
| 行 341: | 行 345: | ||
| $height[1]$ 可以视作 $0$。 | $height[1]$ 可以视作 $0$。 | ||
| - | + | ==== O(n) 求 height 数组需要的一个引理 ==== | |
| - | + | ||
| - | ### $O(n)$ 求 height 数组需要的一个引理 | + | |
| $height[rk[i]]\ge height[rk[i-1]]-1$ | $height[rk[i]]\ge height[rk[i-1]]-1$ | ||
| 行 351: | 行 353: | ||
| 略 | 略 | ||
| - | + | ==== O(n) 求 height 数组的代码实现 ==== | |
| - | + | ||
| - | ### $O(n)$ 求 height 数组的代码实现 | + | |
| 利用上面这个引理暴力求即可： | 利用上面这个引理暴力求即可： | ||
| - | ```c++ | + | <code cpp> |
| for (i = 1, k = 0; i <= n; ++i) { | for (i = 1, k = 0; i <= n; ++i) { | ||
| if (k) --k; | if (k) --k; | ||
| 行 363: | 行 363: | ||
| ht[rk[i]] = k; // height太长了缩写为ht | ht[rk[i]] = k; // height太长了缩写为ht | ||
| } | } | ||
| - | ``` | + | </code> |
| $k$ 不会超过 $n$，最多减 $n$ 次，所以最多加 $2n$ 次，总复杂度就是 $O(n)$。 | $k$ 不会超过 $n$，最多减 $n$ 次，所以最多加 $2n$ 次，总复杂度就是 $O(n)$。 | ||
| - | |||
| - | |||
| 未完待续 | 未完待续 | ||
| + | ===== 参考链接 ===== | ||
| - | + | [[https://oi-wiki.org/string/sa/|参考链接]] | |
| - | ## 参考链接 | + | |
| - | + | ||
| - | [参考链接](https://oi-wiki.org/string/sa/) | + | |
2020-2021/teams/legal_string/后缀数组_lgwza.1595578283.txt.gz · 最后更改: 2020/07/24 16:11 由 lgwza
