算法导论32.3 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 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 δ