算法导论 32.3 Exercises 答案

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

32.3-1

本题的状态集合 $Q = {0, 1, 2, 3, 4, 5}$ ，起始状态 $q_{0} = 0$ ，接受状态为 ${5}$ 。

针对模式串 $P = aabab$ 在字符集 $Σ = {a, b}$ 上的状态函数 $δ (s, c)$ 如下表所示。

$\begin{array}{ccccccc} s & 0 & 1 & 2 & 3 & 4 & 5 \\ a & 1 & 2 & 2 & 4 & 2 & 1 \\ b & 0 & 0 & 3 & 0 & 5 & 0 \end{array}$

由此，对于文本串 $T = aaababaabaababaab$ ，它的状态转移序列为 $0, 1, 2, 2, 3, 4, 5, 1, 2, 3, 4, 2, 3, 4, 5, 1, 2, 3$ ，由此 $P$ 在 $T$ 中出现了两次，分别为偏移量为 $1$ 和 $9$ 时出现。

32.3-2

本题的状态集合 $Q = {0, 1, 2, 3, \dots, 20, 21}$ ，起始状态 $q_{0} = 0$ ，接受状态为 ${21}$ 。

针对模式串 $P = ababbabbababbababbabb$ 在字符集 $Σ = {a, b}$ 上的状态函数 $δ (s, c)$ 如下表所示。

$\begin{array}{ccccccccccccccccccccccc} s & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ a & 1 & 1 & 3 & 1 & 3 & 6 & 1 & 3 & 9 & 1 & 11 & 1 & 3 & 14 & 1 & 16 & 1 & 3 & 19 & 1 & 3 & 9 \\ b & 0 & 2 & 0 & 4 & 5 & 0 & 7 & 8 & 0 & 10 & 0 & 12 & 13 & 0 & 15 & 8 & 17 & 18 & 0 & 20 & 21 & 0 \end{array}$

32.3-3

假设 $P$ 的长度为 $m$ 。 $P [: k] ⊐ P [: q]$ 推导出 $k = 0 \lor k = q$ 意味着这个字符串只要产生了一次失配，那么就必须从头开始匹配，这意味着任何不以 $P [1]$ 为开头的字符串是 $P$ 的一个前缀，因此，这种模式串一般是 $\forall i \in [2, n], P [1] \neq P [i]$ 成立。

对于这种模式串，它的状态转移函数 $δ (s, c) (s \in [0, m], c \in Σ)$ 如下：

$δ (s, c) = {\begin{aligned} 0 & if s = m \lor s < m \land P [s + 1] \neq c \\ s + 1 & if s < c \land P [s + 1] = c \end{aligned}$

32.3-4

由于 $x ⊐ y$ ，因此有 $| x | \leq | y |$ 。又因为 $x, y$ 同为 $P$ 的前缀，因此有 $x ⊏ y$ 。

按照 $σ$ 的定义，有 $σ (x) = | x |$ 。但是因为 $x ⊏ y, x ⊐ y$ ，因此 $σ (y) \geq | x |$ 。最终有 $σ (x) \leq σ (y)$ 。

32.3-5

最少的状态数即为合并 $P$ 和 $P^{'}$ 的最长公共前缀作为共同状态。更一般的说，令 $P$ 和 $P^{'}$ 的最长公共前缀的状态为 $r = max {i : P [: i] = P^{'} [: i]}$ ，那么一共有 $| P | + | P^{'} | - r - 1$ 个状态，直到第 $r$ 个字符之后，状态才会被分开。具体构建过程由 COMPUTE-TRANSITION-FUNCTION' 给出。

COMPUTE-TRANSITION-FUNCTION'(P, m, P', m', ∑)
  r = 0
  while k < m amd k < m' and P[r + 1] == P'[r + 1]
    r += 1
  for q = 0 to m
    for each character a ∈ ∑
      k = min {m, q + 1}
    while P[:k] is not a suffix of P[:q]a
      k = k – 1
      δ(q, a) = k
  for each q = r + 1 to m'
    for each character a ∈ ∑
      k = min {m, q + 1}
    while P'[:k] is not a suffix of P'[:q]a
      k = k – 1
    if k <= r
      δ(q + m, a) = k
    else
      δ(q + m, a) = m + k
  return δ

32.3-6

对于包含通配符 $◊$ 的一个模式串 $P$ ，假设我们将其划分成切割成一个个不包含通配符 $◊$ 的模式串 $P_{1}, P_{2}, \dots, P_{k}$ ，那么将这些状态进行 “首尾相接” 即可，因为只要进行到当前的模式串 $P_{i}$ ，那么就不能转移到以前的模式串。可见将会一共有 $| P | + 1$ 个状态。

具体过程由 COMPUTE-TRANSITION-FUNCTION-GAP 给出。

COMPUTE-TRANSITION-FUNCTION-GAP(P, ∑, m)
  split P into Q[1], Q[2], ..., Q[k] by '◊'
  pre = 0
  for i = 1 to k
    δt = COMPUTE-TRANSITION-FUNCTION-GAP(Q[i], ∑, |Q[i]|)
    for s = 0 to |Q[i]|
      for each character a ∈ ∑
        δ(pre + s, a) = δt(s, a)
    pre = pre + |Q[i]|
  return δ