算法导论 32.4 Exercises 答案

发表于 2023-10-08 分类于算法导论阅读次数： 165 本文字数： 2.9k 阅读时长 ≈ 3 分钟

32.4-1

模式串 $P = ababbabbabbababbabb$ 的前缀数组为 $π = (0, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 3, 4, 5, 6, 7, 8)$ 。

32.4-2

$π^{*} [q]$ 的大小可以达到 $q - 1$ 。以 $m$ 个字符 $a$ 的模式串 $P$ 为例，对于 $\forall q \in [2, n], π^{*} [q] = {1, 2, \dots, q - 1}$ 。因此集合 $π^{*} [q]$ 的大小可以达到 $q - 1$ 。

32.4-3

可见，在 $T$ 中出现 $P$ 的有效偏移量集合为 ${q - 2 m : π [q] = m, q \geq 2 m}$ 。因为 $P$ 被拼接在了前面，因此需要减去 $P$ 已经占有的偏移量 $m$ 。此外，还需要满足 $q \geq 2 m$ ，以避免和字符串 $P$ 有交叉。由于 $π$ 递增时，最多只会递增 $1$ ，因此只需要考虑等于 $m$ 的情况即可满足所有情况，而不需要考虑大于 $m$ 的情况。

32.4-4

不失一般性，这里只考虑 KMP-MATCHER 的主体部分（因为 COMPUTE-PREFIX-FUNCTION 的分析方式和 KMP-MATCHER 一致）。

按照定义，由于 $r = π [q]$ 是 $P [: q]$ 中最长的真子前缀同时也是其后缀，因此 $π [q] < q$ 。这意味着第 4-5 中的 while 循环执行一次 $q$ 值就会减少。由于 $q$ 不可能为负数，并且第 3 行的每轮 for 循环中，只有第 7 行才会对 $q$ 增加（并且只增加 $1$ ），因此第 5 行最多也只会执行 $n$ 次。

最终，第 2-10 行只需要 $Θ (n)$ 的时间即可完成。第 1 行的 COMPUTE-PREFIX-FUNCTION 使用类似分析方式可以得到其运行时间为 $Θ (m)$ 。由于 $m \leq n$ ，因此 KMP-MATCHER 的时间复杂度为 $Θ (m) + Θ (n) = Θ (n)$ 。

32.4-5

本题的分析框架和题目 32.4-4 的一样，只考虑 KMP-MATCHER 的主体部分。

令势函数 $Φ (D_{i})$ 表示第 $i$ 轮 for 循环结束后 $q$ 的值。由于 $q$ 的值在 for 循环开始前为 $0$ ，因此有 $Φ (D_{0}) = 0$ 。

令均摊开销 $\hat{c_{i}} = c_{i} + Φ (D_{i}) - Φ (D_{i - 1})$ ，其中 $c_{i}$ 表示真实开销。那么有 $\sum_{i = 1}^{n} c_{i} = \sum_{i = 1}^{n} \hat{c_{i}} - Φ (D_{n}) + Φ (D_{0})$ 。令每轮开销的均摊代价 $\hat{c_{i}} = 2$ ，那么有

$\begin{aligned} \sum_{i = 1}^{n} c_{i} & = \sum_{i = 1}^{n} \hat{c_{i}} - Φ (D_{n}) + Φ (D_{0}) \\ \leq \sum_{i = 1}^{n} c_{i} + Φ (D_{0}) \\ \leq 2 n \end{aligned}$

因此 KMP-MATCHER 的第 2-10 行只需要 $Θ (n)$ 的时间即可完成。第 1 行的 COMPUTE-PREFIX-FUNCTION 使用类似分析方式可以得到其运行时间为 $Θ (m)$ 。由于 $m \leq n$ ，因此 KMP-MATCHER 的时间复杂度为 $Θ (m) + Θ (n) = Θ (n)$ 。

32.4-6

按照题目给定的 $π^{'}$ 的定义，将 KMP-MATCHER 修改后的 KMP-MATCHER' 如下所示。

COMPUTE-PREFIX-FUNCTION'(P, m)
  π = COMPUTE-PREFIX-FUNCTION(P, m)
  Let π'[1 : m - 1] be a new array
  for q = 1 to m - 1
    if π[q] == 0
      π'[q] = 0
    else if π[q] != 0 and P[π[q] + 1] == P[q + 1]
      π'[q] = π'[π[q]]
    else
      π'[q] = π[q]
  return π, π'

KMP-MATCHER'(T, P, n, m)
  π, π' = COMPUTE-PREFIX-FUNCTION(P, m)
  q = 0
  for i = 1 to n
    while q > 0 and P[q + 1] != T[i]
      q = π[q]
    if P[q + 1] == T[i]
      q = q + 1
    if q == m
      print "Pattern occurs with shift" i – m
      q = π[q]

接下来我们证明这个嵌套调用的 $π^{'}$ 是正确的。如果满足 $π^{'}$ 中定义的第一行和第三行的情况，那么就有 $π^{'} [q] = π [q]$ ，这和 KMP-MATCHER' 执行第 5 行的过程完全一致。

当满足 $π^{'}$ 的第二条情况时，即 $P [q + 1] = P [π [q] + 1]$ ，这种情况意味着在 KMP-MATCHER' 执行第 5 行的过程前后，都将会对 $P [q + 1] \neq T [i]$ 和 $P [π [q] + 1] \neq T [i]$ 进行判断。由于字母相同，这两种判断是没有必要的， $π^{'}$ 将会跳到下一个和 $P [q + 1]$ 不相同的字符 $P [π^{'} [q] + 1]$ 再和 $T [i]$ 进行比较。因此这个过程是正确的。

$π^{'}$ 数组的存在是一个对 KMP-MATCHER 的优化，但是它不会降低 KMP-MATCHER 的时间复杂度。只有当 $T$ 的长度远大于 $P$ 的长度时， $π^{'}$ 数组会对 KMP-MATCHER 带来常数上的优化。 # 32.4-7

$T$ 是 $T^{'}$ 的旋转串，当且仅当 $T^{'}$ 出现在 $T T$ 中。因此这相当于执行了一次 KMP-MATCHER 算法。具体过程由 IS-CYCLIC-ROTATION 给出。

IS-CYCLIC-ROTATION(T, T', m)
  π = COMPUTE-PREFIX-FUNCTION(P, m)
  q = 0
  S = TT
  for i = 1 to m + m
    while q > 0 and T[q + 1] != S[i]
      q = π[q]
    if T[q + 1] == S[i]
      q = q + 1
    if i > m and q == m
      print "T' is T with shift" i – m
      q = π[q]

$⋆$ 32.4-8

基于 KMP 算法的 $π$ 数组计算转移函数 $δ$ 的算法由 COMPUTE-TRANSITION-FUNCTION-KMP 所示。

COMPUTE-TRANSITION-FUNCTION-KMP(P, ∑, m)
  π = COMPUTE-PREFIX-FUNCTION(P, m)
  for each character a ∈ ∑
    δ(0, a) = 0
  δ(0, P[1]) = 1
  for q = 1 to m
    for each character a ∈ ∑
      if q < m and P[q + 1] == a
        δ(q, a) = q + 1
      else
        δ(q, a) = δ(π[q], a)
  return δ

可见第 2-4 行对 $δ (0, \cdot)$ 处理的正确性是显而易见的，在一开始没有接受到任何字符时，只有接受到正确的字符 $P [1]$ 时，才可以从状态 $0$ 转移到状态 $1$ 。第 7-8 行的处理同样也是显而易见的，遇到正确的字符那么就向前一个状态进位。

接下来证明另一种情况，即第 9-10 行的情况。按照 $δ$ 的定义，可见 $δ (q, a) = σ (P [: q] a)$ ，将 $π [q]$ 视为前面的 $q$ ，也有 $δ (π [q], a) = σ (P [: π [q]] a)$ 。按照 $π$ 数组的定义，由于 $P [: π [q]] ⊐ P [: q]$ ，因此 $P [: π [q]] a ⊐ P [: q] a$ ，从而 $σ (P [: π [q]] a) \leq σ (P [: q] a)$ 。由于 $π [q] = σ (P [: q])$ ，因此 $P [: q]$ 后面添加一个字符 $a$ 后，可以得到 $π [q] \geq σ (P [: q] a) - 1$ ，因为 $σ$ 的函数值最多只会增加 $1$ ，这意味着 $σ (P [: π [q]] a) \geq σ (P [: q] a)$ 。

因此，最终可以得到 $σ (P [: π [q]] a) = σ (P [: q] a)$ ，即 $δ (π [q], a) = δ (q, a)$ ，原结论成立。