算法导论32.4 Exercises 答案

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

32.4-1

模式串$P=\texttt{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$个字符$\texttt{a}$的模式串$P$为例，对于$\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行只需要$\Theta(n)$的时间即可完成。第1行的COMPUTE-PREFIX-FUNCTION使用类似分析方式可以得到其运行时间为$\Theta(m)$。由于$m\le n$，因此KMP-MATCHER的时间复杂度为$\Theta(m)+\Theta(n)=\Theta(n)$。

32.4-5

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

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

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

$\begin{aligned}
\sum{i=1}^nc_i&=\sum{i=1}^n\widehat{ci}-\Phi(D_n)+\Phi(D_0)\
&\le \sum{i=1}^nc_i+\Phi(D_0)\
&\le 2n
\end{aligned}$

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

32.4-6

按照题目给定的$\pi’$的定义，将KMP-MATCHER修改后的KMP-MATCHER'如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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’$是正确的。如果满足$\pi’$中定义的第一行和第三行的情况，那么就有$\pi’[q]=\pi[q]$，这和KMP-MATCHER'执行第5行的过程完全一致。

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

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

32.4-7

$T$是$T’$的旋转串，当且仅当$T’$出现在$TT$中。因此这相当于执行了一次KMP-MATCHER算法。具体过程由IS-CYCLIC-ROTATION给出。

1
2
3
4
5
6
7
8
9
10
11
12
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所示。

1
2
3
4
5
6
7
8
9
10
11
12
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]]\sqsupset P[:q]$，因此$P[:\pi[q]]a\sqsupset 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)$，原结论成立。