1_金策_字符串算法选讲.pdf

字符串算法选讲 . . 字符串算法选讲 金策 清华大学交叉信息研究院 February 3, 2017 字符串算法选讲 Periods and borders Basics 字符串: s[1..n], |s| = n。 字符集: s[i] ∈ Σ。算法竞赛中常见的 Σ 是 26 个小写英文字 母。 子串 s[i..j] = s[i]s[i + 1] · · · s[j]。 前缀 pre(s, x) = s[1..x], 后缀 suf(s, x) = s[n − x + 1..n]。 字符串算法选讲 Periods and borders Basics 周期和 border 若 0 < p ≤ |s|, s[i] = s[i + p], ∀i ∈ {1, · · · , |s| − p}, 就称 p 是 s 的周期 (period)。 若 0 ≤ r < |s|, pre(s,r) = suf(s,r), 就称 pre(s,r) 是 s 的 border。 pre(s,r) 是 s 的 border ⇔ |s|−r 是 s 的周期。 u period . border 比如 abaaaba 就有周期 4, 6, 7, 对应的 border 是 aba,a, 和 ε。 字符串算法选讲 Periods and borders Basics KMP 算法 可以在 O(n) 时间求出数组 fail[1..n], 其中 fail[i] 表示前缀 s[1..i] 的最大 border 长度。 s 的所有 border 长度? {fail[n], fail[fail[n]], · · · } 字符串算法选讲 Periods and borders Basics 后缀数组和 LCP 查询 在 O(n log n) 时间空间预处理后(或较复杂的 O(n) 时间空间 预处理), 可以 O(1) 回答: 两个子串的最长公共前缀 (LCP)、最 长公共后缀 (LCS)。 对于拥有周期 p 的串 s, LCP(s[1..n], s[1 + p..n]) = n − p。 输入 i, O(1) 回答最大的 l 使得 s[i..i+l−1] 拥有周期 p。