算法导论 32.3 Exercises 答案

发表于 分类于 本文字数： 2.2k 阅读时长 ≈ 2 分钟

32.3-1

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

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

s012345a122421b003050

由此，对于文本串 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,…,20,21}，起始状态 q0=0，接受状态为 {21}。

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

s0123456789101112131415161718192021a11313613911113141161319139b020450780100121301581718020210

32.3-3

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

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

δ(s,c)={0ifs=m∨s<m∧P[s+1]≠cs+1ifs<c∧P[s+1]=c

32.3-4

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

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

32.3-5

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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，假设我们将其划分成切割成一个个不包含通配符 ◊ 的模式串 P1,P2,…,Pk，那么将这些状态进行 “首尾相接” 即可，因为只要进行到当前的模式串 Pi，那么就不能转移到以前的模式串。可见将会一共有 |P|+1 个状态。

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

1
2
3
4
5
6
7
8
9
10
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 δ