算法导论32 Problems 答案

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

32-1

a

首先使用KMP算法计算出$\pi$数组，分两种情况进行考虑：

如果$i\bmod (i-\pi[i])=0$，那么有$\rho(P[:i])=\dfrac{i}{i-\pi[i]}$，这意味$P[i-\pi[i]+1:i]=P[1:\pi[i]]$，那也就是说，$P[\pi[i]+1:2\pi[i]]=P[1,\pi[i]]$，类似的，有$P[i-2\pi [i]+1:i]=P[i-\pi [i]+1:i]$，最终多次迭代下去，可以发现这是一个周期为$\dfrac{i}{i-\pi[i]}$的字符串，此外，由于$\forall k\in \pi^{\ast}[i]$，都有$k\le \pi[i]$，因此$i-\pi[i]$是$i$满足条件的最小因子，它将使值$\dfrac{i}{i-k}$达到最大，因此原结论成立。
如果$i\bmod (i-\pi[i])\neq 0$，那么$\rho(P[:i])=1$。因为，对于一个非周期字符串$s$（如果是周期字符串，那么可以归约到最小非周期字符串），如果存在一个正整数$r$满足$s^r=P[i]$，那么有$r\mid i$。然而按照上面的方式依次取出$r$个字母，它们不能取完整，因此这时$P[:i]$只能由自身拼接$1$次而成，原结论成立。

算法COMPUTE-PREFIX-RHO给出了具体过程，可见其时间复杂度为$O(n)$。

COMPUTE-PREFIX-RHO(P, m)
  π = COMPUTE-PREFIX-FUNCTION(P, m)
  let ρ[1 : m] be a new array
  for i = 1 to m
    if i % (i - π[i]) == 0
      ρ[i] = i / (i - π[i])
    else
      ρ[i] = 1
  return ρ

b

待研究，相关链接：

c

同题目32-1-b。

32-2

a

假设目前需要对比$P$中非空后缀$i$和$j$，令$P[i]$表示$P$的第$i$个元字符。如下考虑多种情况：

如果$P[i]\neq P[j]$，那么第$i$个非空后缀和第$j$个非空后缀的字典序由$P[i]$和$P[j]$决定，此时和$P[i],P[j]$后面的字符没有任何关系，因此原结论成立。
如果$P[i]=P[j]$，考虑$i,j$都在$P$中$P_1$所占有的下标。可见，由于$P_1[i:]\varnothing$和$P_1[j:]\varnothing$的长度不同，并且最后一个字符$\varnothing$都小于已经出现的字符，因此它们的字典序已经确定。此时再在独立的字符串$P_1[i:]\varnothing,P_1[j:]\varnothing$后面再添加字符也不会改变$P_1[i:]\varnothing$和$P_1[j:]$的字典序。因此原结论成立。接下来考虑$i,j$都在$P$中$P_2$所占有的下标，明显原结论成立，因为这些后缀恰好是$P_2$的后缀。
如果$P[i]=P[j]$，考虑$i,j$在$P$中，其中一个在$P_1$所占有的下标，另一个在$P_2$所占有的下标。不失一般性，假设$i$属于前者，$j$属于后者，那么不难得到$i<j$。由于此时$P[i]=P[j]$，因此我们继续向下找下一个下标，直到满足这两个元字符不相同，即最小的正整数$s$，使得$P[i+s]\neq P[j+s]$。可以发现$i+s$仍会在$P_1$占有的下标中。按照步骤A的作用，$P_1$必定会包含一个出现$\varnothing$的元字符，因此第$i$个非空后缀不晚于这个元字符结束。由于$n'\not\equiv n''\pmod 3$，因此$i$个非空后缀和第$j$个非空后缀必定是以不同数量的$\varnothing$元字符作为结尾，此外由于$\varnothing$的字典序最小，再在它们的后面任意添加字符也不会改变这两个非空后缀的字典序，因此原结论成立。

因此，$P$的非空后缀的排名和$P$的后缀排名是相同的。由于早在$\varnothing$的时候就已经确定了排名，去除$\varnothing$后面的字符并不影响后缀的排名，因此$P$中的后缀排名和$T$的采样后缀的相对排名是一致的，因此原结论成立。

b

由于每个元字符都恰好是一个三元组，因此我们可以使用基数排序完成，只需要进行三趟。由于字符的大小有限，因此每趟基数排序的内部使用计数排序，最终可以在$\Theta(n)$的时间内完成这个排序过程。需要注意的是，由于前面的字符占主导地位，因此基数排序过程是对这些三元组中的每个字符从后往前进行。如下算法SA-SORT-CHARACTERS给出了这个过程，可见其时间复杂度为$\Theta(n)$。

// 假设字符出P中的每个字符用三元组(s[1], s[2], s[3])表示，分别表示元字符中的第一、第二和第三个字符。
SA-SORT-CHARACTERS(P, n)
  // L数组中的元素有两个属性：s属性是对应下标的元字符，index属性表示当前字符的下标。
  let L[1 : n], L'[1 : n], P'[1 : n] be new arrays
  for i = 1 to n
    L[i].index = i
    L[i].s = P[i].s
  mx = 0
  // 这里使用mx表示元字符中，所有内部字符的最大大小。
  for i = 1 to n
    mx = max{mx, P[i].s[1], P[i].s[2], P[i].s[3]}
  let cnt[0 : mx] be a new array
  for d = 3 downto 1
    for j = 0 to mx
      cnt[j] = 0 
    for i = 1 to n
      cnt[L[i].s[d]] = cnt[L[i].s[d]] + 1
    for j = 1 to mx
      cnt[j] = cnt[j - 1] + cnt[j]
    for i = n downto 1
      L'[cnt[L[i].s[d]]] = L[i]
      cnt[L[i].s[d]] = cnt[L[i].s[d]] - 1
    L = L'
  r = 1
  P'[L[1].index] = 1
  for i = 2 to n
    if L[i].s != L[i - 1].s
      r = r + 1
    P'[L[i].index] = r
  return P'

c

假设后缀$P[i:]$是非采样后缀，那么有$r_i=\square,r_{i+1}$是一个非负整数。如果$r_i\neq \square$，那么说明$r_i$是进行递归后，对应采样后缀的排名，因此这些$r_i$是非负整数的情况下是唯一的，因此这使得二元组$(T[i],r_{i+1})$是唯一的。

由于原字符$T[i]$的范围非常小，因此我们同样可以使用题目32-2-b的思路，使用基数排序（每趟内部使用计数排序）对这些二元组进行排序。如下算法SA-SORT-CHARACTERS给出了这个过程，可见其时间复杂度为$\Theta(n)$。

SA-SORT-NONSAMPLE-SUFFIXES(T, r, n)
  n' = ⌊n / 3⌋
  let L[1 : n'], L'[1 : n'], nonsapmle[1 : n'] be new arrays
  for i = 3 to n by 3
    let L[i / 3].t[1 : 2] be a new array
    L[i / 3].t[1] = T[i]
    L[i / 3].t[2] = r[i + 1]
    L[i / 3].index = i
  mx = 0
  // 这里使用mx表示元字符中，所有字符的大小。
  for i = 1 to n'
    mx = max{mx, L[i].t[1], L[i].t[2]}
  let cnt[0 : mx] be a new array
  for d = 2 downto 1
    for j = 0 to mx
      cnt[j] = 0 
    for i = 1 to n'
      cnt[L[i].t[d]] = cnt[L[i].t[d]] + 1
    for j = 1 to mx
      cnt[j] = cnt[j - 1] + cnt[j]
    for i = n' downto 1
      L'[cnt[L[i].s[d]]] = L[i]
      cnt[L[i].s[d]] = cnt[L[i].s[d]] - 1
    L = L'
  return L

d

假设字符串$T$后面已经拼接了两个$\varnothing$，对应到$r$数组中其值为$0$，也就是说，字符串$T$现在的长度为$n+2$。

其基本思想是，对于任意一对下标$i,j(i\not\equiv j\pmod 3,1\le i,j\le n)$，只要最多比较三次就能比较出字典序。也就是说，只要比对$(P[i],P[j]),(P[i+1],P[j+1]),(P[i+2],P[j+2])$即可。可以发现，必定存在最小的$s(0\le s\le 2)$，使得$r_{i+s}\neq\square\land r_{j+s}\neq\square$。

具体过程由SA-SORT-MERGE给出，它将原有的$r$数组以及题目32-2-d所排好序的二元组进行归并，返回最终得到的$SA$数组。最终这个过程在$\Theta(n)$的时间内完成。

// 字符串T的长度为n+2，包括后面已经拼接了两个∅，r[n + 1] = r[n + 2] = 0。
// 数组r如题意所示。
// 数组nonsample是已经排好序的非采样后缀的下标，保证其大小为⌊n / 3⌋。
SA-SORT-MERGE(T, r, nonsample, n)
  n' = ⌊n / 3⌋
  sample-choice = 1
  nonsample-choice = 2
  let sample[1 : n - n'] be a new array
  for i = 1 to n
    if i % 3 != 0
      sample[r[i]] = i
  let SA[1 : n] be a new array
  ls = 1
  ln = 1
  k = 1
  while ls <= n - n' and ln <= n'
    p = sample[ls]
    q = nonsample[ln]
    if T[p] != T[q]
      if T[p] < T[q]
        choice = sample-choice
      else
        choice = nonsample-choice
    else if p % 3 == 1
      // 此时r[p + 1] != □必定成立
      if r[p + 1] < r[q + 1]
        choice = sample-choice
      else
        choice = nonsample-choice
    else
      // 此时r[p + 1] != □必定成立
      if T[p + 1] < T[q + 1] or T[p + 1] == T[q + 1] and r[p + 2] < r[q + 2]
        choice = sample-choice
      else
        choice = nonsample-choice
    if choice == sample-choice
      SA[k] = p
      k = k + 1
      ls = ls + 1
    else
      SA[k] = q
      k = k + 1
      ln = ln + 1
  while ls <= n - n'
    SA[k] = sample[ls]
    k = k + 1
    ls = ls + 1
  while ls <= n'
    SA[k] = nonsample[ls]
    k = k + 1
    ln = ln + 1
  return SA

e

综上所述：

步骤1进行的是第一步分治。子步骤A和B花费了$\Theta(n)$的时间来构造字符串$P,P_1,P_2$。子步骤C使用了题目32-2-b的算法，对字符串$P$中的字符进行排序，并通过子步骤D进行产生$P$中每个字符的排名，存在数组$P'$中，这个过程使用了基数排序和计数排序的方法，总共花费了$\Theta(n)$的时间。子步骤E递归构造$P'$的$SA$数组，由于其长度为$2n/3$，因此需要花费$T(2n/3)$的时间。子步骤F则使用$\Theta(n)$的时间将$P'$的$SA$数组映射回采样后缀中。
步骤2进行的是第二步分治。子步骤G使用$\Theta(n)$的时间求出$r$数组。子步骤H使用了题目32-2-c的算法，对$(T[i],r_{i+1})$二元组进行排序，由于同样使用了基数排序和计数排序的方法，因此总共花费了$\Theta(n)$的时间。
步骤3进行的是归并。它将两个分支步骤的结果进行归并。使用题目32-2-d的算法在$\Theta(n)$时间内求出最终的$SA$数组。

因此，除了步骤1的子步骤E需要求解规模为$2n/3$的子问题，其余步骤都需要花费$\Theta(n)$的时间进行处理，因此有$T(n)=T(2n/3)+\Theta(n)$。按照主定理，有$T(n)=\Theta(n)$，因此这是一个线性时间求解$SA$数组的算法。

32-3

a

需要注意的是，拼接的字符$\mathtt{\$}$的字典序是所有字符中最小的。可以假定，在为字符串构造SA数组时，它后面都有一个终结符$\mathtt{\$}$。因此，在对所有后缀排好序后，可以发现每个后缀的排名都是唯一的，此时在这些后缀后面如何加字符，都不会影响它们原本的排名。因此，BWT只需要挪用$SA$数组的结果即可，不过需要先在$SA$数组的最前面再插入一个值$|T|+1$，那么这时的结果才是BWT数组产生的结果。最终，字符串$t[i]=T[(BWT [i]-1-1)\bmod (|T|+1) + 1]$才是BWT的结果。更具体的过程由BWT-KNOWN-SA给出。

BWT-KNOWN-SA(T, SA, n)
  let BWT[1 : n + 1] be a new array
  W = T$
  t = T[n]
  for i = 1 to n
    t = t W[(SA[i] - 1 - 1) mod (n + 1) + 1]
  return t

b

基于插入排序的思想就可以计算出每个下标的排名，如下给出BWT-COMPUTE-RANK将给出计算$rank$数组的算法。如果字母表中一共有$k$个字符，并且其范围是从$1$到$k$，那么BWT-COMPUTE-RANK计算$rank$数组的时间复杂度为$\Theta(n+k)$。如果$k=O(n)$或者是一个常数，那么就有$\Theta(n+k)=\Theta(n)$。

BWT-COMPUTE-RANK(T, n, k)
  let C[0 : k], rank[1 : n] be new arrays by 0
  for i = 1 to n
    C[T[i]] = C[T[i]] + 1
  for i = 1 to k
    C[i] = C[i] + C[i-1]
  for i = n downto 1
    rank[i] = C[T[i]]
    C[T[i]] = C[T[i]] - 1
  return rank

c

只需要按照题目的含义进行模拟即可，先从$\mathtt{\$}$开始填充，因为它必定处于最后一位。整个过程由BWT-INV给出，可见其由于只有一个for循环进行常数操作，因此其时间复杂度为$\Theta O(n)$。

BWT-INV-RANK(T, rank, n)
  let S[1 : n] be a new array
  pos = 0
  for i = 1 to n
    if T[i] == $
      pos = i
  for i = n downto 1
    S[i] = T[pos]
    pos = rank[pos]
  interpret S[1 : n - 1] as a string s
  return s