算法导论32.4 Exercises 答案

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

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{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1})\)，其中\(c_i\)表示真实开销。那么有\(\displaystyle{\sum_{i=1}^nc_i=\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{c_i}-\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'如下所示。

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给出。

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所示。

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)\)，原结论成立。