算法导论 32.1 Exercises 答案

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

32.1-1

令 t(s)(s≤n−m) 表示偏移为 s 时，进行的匹配次数，那么这些匹配次数由下表给出：

s000010001010001t(s)is matched000014No1 00014Yes2  00013No3   00012No4    00011No5     00014Yes6      00013No7       00012No8        00011No9         00012No10          00011No11           00014Yes

32.1-2

如果 P 的各个字母都不相同，那么可以考虑从左到右遍历文本串 T，考察 T 中和 P[1] 相同的那些下标。由于 P 中的字符各不相同，因此对于一对相邻都是字符 P[1] 的下标 i,j(i<j)，只有 i+|P|≤j 时，偏移量 i+1 才有可能是正确的，这时只需要检测一下即可。

由于 S 中的每个字符和 P 中的字符至多只会进行一次匹配，因此这个算法的时间复杂度为 O(n)。具体过程由 NAIVE-STRING-MATCHER' 给出。

1
2
3
4
5
6
7
8
9
NAIVE-STRING-MATCHER(T, P, n, m)
  cnt = n + 1
  for i = 1 to n
    if T[i] == P[1]
      cnt = 1
    else
      cnt = cnt + 1
    if cnt == m and P[1:m] == T[i - cnt + 1:i]
      print "Pattern occurs with shift" i - cnt

32.1-3

对于文本串 T 的偏移量 s，它能和模式串 P 的第 j 个字符比较当且仅当 T[s+1:s+j−1]=P[1:j−1]，这个概率值为 d−(j−1)。

令随机变量 Xs 表示偏移量为 s 时，T[s+j−1] 和 P[j] 发生了比较。那么有 Xs,j=d−(j−1)。

令随机变量 Y=∑s=0n−m∑j=1mXij 表示比较次数，那么有：

E[Y]=∑s=0n−m∑j=1mE[Xij]=∑s=0n−m∑j=1m1dj−1=∑s=0n−md−d1−md−1=(n−m+1)⋅d−d1−md−1=(n−m+1)⋅1−dm1−d−1≤(n−m+1)⋅11−d−1≤(n−m+1)⋅11−2−1≤2(n−m+1)

32.1-4

本题可以使用动态规划进行求解。令状态 f(i,j)(0≤i≤m,0≤j≤m) 表示使用 P 的前 i 个字符是否能匹配 T 的前 j 个字符。那么可以写出如下状态转移方程：

f(i,j)={1ifi=0∧j=00ifi=0∧j>0∨i>0∧j=0∧P[i]≠◊∧f(i−1,0)=0⋁k=0jf(i−1,k)ifi>0∧P[i]=◊f(i−1,j−1)∧1{P[i]=S[j]}ifi>0∧j>0∧P[i]≠◊

其中 1{b} 表示一个示性函数，用于表示布尔表达式 b 是否成立。方程第三行表示这里有一个通配符 ◊，它可以匹配任意长度的字符串，因此可以从任意状态 f(i−1,k) 转移到 f(i,j)(k≤j)，方程的第四行用于表示一个普通字符的匹配。

最终答案为 f(m,n)。

使用前缀和可以将这个转移优化到 O(nm)，因此可以在多项式时间复杂度内完成这个问题。