算法导论 32.4 Exercises 答案

32.4-1

模式串 $P=\mathtt{\text{ababbabbabbababbabb}}$ 的前缀数组为 $\pi =(0,0,1,2,0,1,2,0,1,2,0,1,2,3,4,5,6,7,8)$。

32.4-2

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

32.4-3

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

32.4-4

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

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

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

32.4-5

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

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

令均摊开销 $\widehat{c_i}=c_i+\mathrm{\Phi }(D_i)-\mathrm{\Phi }(D_{i-1})$，其中 $c_i$ 表示真实开销。那么有 ${\displaystyle \sum _{i=1}^n{c}_i=\sum _{i=1}^n\widehat{c_i}-\mathrm{\Phi }(D_n)+\mathrm{\Phi }(D_0)}$。令每轮开销的均摊代价 $\widehat{c_i}=2$，那么有

$\begin{array}{rl}\sum _{i=1}^n{c}_i& =\sum _{i=1}^n\widehat{c_i}-\mathrm{\Phi }(D_n)+\mathrm{\Phi }(D_0)\\ & \le \sum _{i=1}^n{c}_i+\mathrm{\Phi }(D_0)\\ & \le 2n\end{array}$

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

32.4-6

按照题目给定的 ${\pi }^{\prime }$ 的定义，将 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]

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

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

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

$T$ 是 $T^{\prime }$ 的旋转串，当且仅当 $T^{\prime }$ 出现在 $TT$ 中。因此这相当于执行了一次 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]

$\star$ 32.4-8

基于 KMP 算法的 $\pi$ 数组计算转移函数 $\delta$ 的算法由 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 行对 $\delta (0,\cdot )$ 处理的正确性是显而易见的，在一开始没有接受到任何字符时，只有接受到正确的字符 $P[1]$ 时，才可以从状态 $0$ 转移到状态 $1$。第 7-8 行的处理同样也是显而易见的，遇到正确的字符那么就向前一个状态进位。

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

因此，最终可以得到 $\sigma (P[:\pi [q]]a)=\sigma (P[:q]a)$，即 $\delta (\pi [q],a)=\delta (q,a)$，原结论成立。