算法导论 32.5 Exercises 答案

发表于 分类于 本文字数： 10k 阅读时长 ≈ 9 分钟

32.5-1

如下两表，是分别执行完 COMPUTE-SUFFIX-ARRAY 的第 2-7 行和第 8 行后的结果。

ileft-rankright-rankindexsubstring1891hi29162ip316163pp41694pi59205it620256ty72587yh88158ho915169op10161610pp1116911pi1292012it13202513ty1425014yileft-rankright-rankindexsubstring1891hi28158ho39162ip49205it592012it615169op71694pi816911pi916163pp10161610pp1120256ty12202513ty1325014y142587yh

当 l=2 时，分别执行完 COMPUTE-SUFFIX-ARRAY 的第 11 行，第 12-17 行和第 18 行的结果如下三个表所示。

iranksubstring11hi23ip37pp46pi54it68ty710yh82ho95op107pp116pi124it138ty149yileft-rankright-rankindexsubstring1171hipp2362ippi3743ppit4684pity54105ityh6826tyho71057yhop8278hopp9569oppi107410ppit116811pity124912ity138013ty149014yileft-rankright-rankindexsubstring1171hipp2278hopp3362ippi44912ity54105ityh6569oppi7684pity86811pity9743ppit107410ppit118013ty12826tyho139014y141057yhop

当 l=4 时，分别执行完 COMPUTE-SUFFIX-ARRAY 的第 11 行，第 12-17 行和第 18 行的结果如下三个表所示。

iranksubstring11hipp23ippi38ppit47pity55ityh610tyho712yhop82hopp96oppi108ppit117pity124ity139ty1411yileft-rankright-rankindexsubstring1151hippityh23102ippityho38123ppityhop4724pityhopp5565ityhoppi61086tyhoppit71277yhoppity8248hoppity9699oppity1081110ppity117011pity124012ity139013ty1411014yileft-rankright-rankindexsubstring1151hippityh2248hoppity33102ippityho44012ity5565ityhoppi6699oppity77011pity8724pityhopp981110ppity108123ppityhop119013ty121086tyhoppit1311014y141277yhoppity

当 l=8 时，分别执行完 COMPUTE-SUFFIX-ARRAY 的第 11 行，第 12-17 行和第 18 行的结果如下三个表所示。

iranksubstring11hippityh23ippityho310ppityhop48pityhopp55ityhoppi612tyhoppit714yhoppity82hoppity96oppity109ppity117pity124ity1311ty1413yileft-rankright-rankindexsubstring1161hippityhoppity2392ippityhoppity31073ppityhoppity4844pityhoppity55115ityhoppity612136tyhoppity71407yhoppity8208hoppity9609oppity109010ppity117011pity124012ity1311013ty1413014yileft-rankright-rankindexsubstring1161hippityhoppity2208hoppity3392ippityhoppity44012ity55115ityhoppity6609oppity77011pity8844pityhoppity99010ppity101073ppityhoppity1111013ty1212136tyhoppity1313014y141407yhoppity

因此，得到的 SA 数组为 [1,8,2,12,5,9,11,4,10,3,13,6,14,7]。

最终，按序填入 LCP 数组的顺序如下表所示：

i1234567891011121314s1310851214269741113LCP[i]00543211010100

因此，得到的 LCP 数组为 [0,1,0,1,3,0,0,4,1,5,0,2,0,1]。

32.5-2

基本思想是，如果不需要 ⌊lg⁡n⌋−1 次 while 循环就能够区分出所有后缀的排名，那么 while 循环可以提前终止。

具体细节是，在 MAKE-RANKS 的过程中，如果最后一名的后缀的排名已经恰好达到了 n，那么可以终止 while 循环。修改狗的算法由 COMPUTE-SUFFIX-ARRAY' 给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
COMPUTE-SUFFIX-ARRAY'(T, n)
  allocate arrays substr-rank[1:n], rank[1:n], and SA[1:n]
  for i = 1 to n
    substr-rank[i].left-rank = ord(T[i])
    if i < n
      substr-rank[i].right-rank = ord(T[i + 1])
    else substr-rank[i].right-rank = 0
    substr-rank[i].index = i
  sort the array substr-rank into monotonically increasing order based on the left-rank attributes, using the right-rank attributes to break ties; if still a tie, the order does not matter
  l = 2
  while l < n
    MAKE-RANKS(substr-rank, rank, n)
    for i = 1 to n
      substr-rank[i].left-rank = rank[i]
      if i + l ≤ n
        substr-rank[i].right-rank = rank[i + l]
      else substr-rank[i].right-rank = 0
      substr-rank[i].index = i
    sort the array substr-rank into monotonically increasing order based on the left-rank attributes, using the right-rank attributes to break ties; if still a tie, the order does not matter
    l = 2 * l
  for i = 1 to n
    SA[i] = substr-rank[i].index
  return SA

32.5-3

使用一个不曾出现在 T1,T2 中的字符 @，并将其和 T1,T2 拼接起来，得到 T=T1@T2，其长度为 n=n1+n2+1。对字符串 T 求出它的 SA 数组和 LCP 数组后，枚举 T 中每对排名相邻的后缀 SA[i],SA[i−1]。如果这两个后缀来自 T 的不同部分（也就是其中一个来自 T1，另一个来自 T2）那么说明这两个后缀的最长公共前缀为 T1,T2 这两个字符串的子串之一，由于 @ 不在 T1 中，因此可以确保 LCP 不会恰好经过 @。具体过程由程序 LONGEST-COMMON-SUBSTRINGS 给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LONGEST-COMMON-SUBSTRINGS(T1, T2, n1, n2)
  T = T1 @ T2
  n = n1 + n2 + 1
  SA = COMPUTE-SUFFIX-ARRAY(T, n)
  LCP = COMPUTE-LCP(T, SA, n)
  len = 0
  S = ∅
  for i = 2 to n
    l = SA[i - 1]
    r = SA[i]
    if min{l, r} <= n1 and max(l, r) > n1 + 1
      if LCP[i] > len
        len = LCP[i]
        S = {min{l, r}}
    else if lCP[i] == len
        S = S ∪ {min{l, r}}
  let string-list be a new array
  for l in S
    INSERT(string-list, T1[l : l + len - 1])
  return string-list

32.5-4

这里首先需要解释一下这个约束 SA[i−1]=n′−SA[i]−LCP[i]+2 是怎么来的：

首先，T 中有一个子串 [l,r] 是回文串，那么在 T′ 这个字符串中，其在后半段对应的位置中是 [l′,r′]。这意味着 r−l+1=r′−l′+1=len，由于 T′ 的最后 n 个字符是由 T 反转而来，并且字符 @ 处在下标 n′+12 中，因此有 n′+12−r=l′−n′+12。最终联立上面两个式子可以得到 n′+1=l′+l+len−1，更进一步可以得到 l′=n′−l−len+2，和上面给定的约束很像。

因此，这个求解最长回文子串的算法的错误在于，它认为后缀 T[l:] 和 T[l′:] 在 SA 数组中是相邻的，然而并非如此。

考虑字符串 T=abbcabb，那么有 T′=abbcabb@bbacbba。等算法结束后，我们可以得到关于这个字符串的表格：

iSA[i]substringLCP[i]SA[i−1]=n′−SA[i]−LCP[i]+218@bbacbba0No215a0No35abb@bbacbba1No41abbcabb@bbacbba3No511acbba1No67b@bbacbba0No714ba1No810bacbba2No96bb@bbacbba1Yes1013bba2No119bbacbba3No122bbcabb@bbacbba2No133bcabb@bbacbba1No144cabb@bbacbba0No1512cbba1Yes

由表格可知这个算法的输出结果为 1，但是实际上答案为 2。T 一共有两个子串 bb 满足答案。其中一对 bb 及其在后半段的反转分别是 T′[2:3],T′[13:14]，但是在 SA 数组中，2 和 13 不相邻。同样的，另一对 bb 则及其反转分别是在 T′[6:7],T′[9:10]，但是在 SA 数组中，6 和 10 不相邻。

最终是因为约束 SA[i−1]=n′−SA[i]−LCP[i]+2 认为后缀 T[l:] 和 T[l′:] 在 SA 数组中是相邻的，导致了错误。因此这个约束不正确。