算法导论32.3 Exercises 答案

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

32.3-1

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

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

\(\begin{array}{|c|c|c|c|c|c|c|}\hline s&0&1&2&3&4&5\\\hline \texttt{a}&1&2&2&4&2&1\\\hline \texttt{b}&0&0&3&0&5&0\\\hline \end{array}\)

由此，对于文本串\(T=\texttt{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=\texttt{ababbabbababbababbabb}\)在字符集\(\Sigma=\{a,b\}\)上的状态函数\(\delta(s,c)\)如下表所示。

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

32.3-3

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

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

\(\delta(s,c)= \left \{\begin{aligned} &0 & & \text{if}\quad s=m\lor s<m \land P[s+1]\neq c \\ &s+1 & & \text{if}\quad s<c\land P[s+1]=c \\ \end{aligned}\right.\)

32.3-4

由于\(x\sqsupset y\)，因此有\(|x|\le |y|\)。又因为\(x,y\)同为\(P\)的前缀，因此有\(x\sqsubset y\)。

按照\(\sigma\)的定义，有\(\sigma(x)= |x|\)。但是因为\(x\sqsubset y,x\sqsupset y\)，因此\(\sigma(y)\ge |x|\)。最终有\(\sigma(x)\le \sigma(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

对于包含通配符\(\Diamond\)的一个模式串\(P\)，假设我们将其划分成切割成一个个不包含通配符\(\Diamond\)的模式串\(P_1,P_2,\dots,P_k\)，那么将这些状态进行“首尾相接”即可，因为只要进行到当前的模式串\(P_i\)，那么就不能转移到以前的模式串。可见将会一共有\(|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 δ