算法导论32.2 Exercises 答案

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

32.2-1

可见，\(p=26\bmod 11=4\)。

按照算法RABIN-KARP-MATCHER的执行结果，可以计算出的\(t_s\)值如下标：

\(\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline s&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14\\\hline t_s&9&3&8&4&4&4&4&10&9&2&3&1&9&2&5\\\hline \end{array}\)

可见一共有\(4\)次命中，但是仅有偏移\(6\)是有效偏移，因此其余的偏移\(3,4,5\)都是伪命中。

32.2-2

这题的思想比较简单：首先求出\(k\)个模式串的\(p\)值\(p_1,p_2,\dots,p_k\)，并且使用一个基于链接法的哈希表来存储这些\(p\)值和对应的字符串。只要哈希表的大小合适，那么只需要\(O(1)\cdot O(m(v+n/q))= O(m(v+n/q))\)，其中\(v\)是有效偏移的数量。需要注意的是，只有\(p_1,p_2,\dots,p_k\)都是长度为\(m\)的情况下才能使用该算法RABIN-KARP-MATCHER'：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
RABIN-KARP-MATCHER'(T, P, n, k, m, d, q)
  h = d^(m - 1) mod q
  let p[1 : k] be a new array by 0
  let T be a new hash-table.
  t0 = 0
  for i = 1 to m
    t0 = (d * t0 + T[i]) mod q
    for j = 1 to k
    p[j] = (d * p[j] + P[j, i]) mod q
  for j = 1 to k
    let x be a new node
    x.key = p[j]
    x.p = P[j]
    // 节点x存的是字符串和它的哈希值。
    CHAINED-HASH-INSERT(T, x)
  //假设CHAINED-HASH-SEARCH'返回的是哈希表中和x.key相同的所有节点，而并非只是至多一个；hash是一个哈希函数。
  for s = 0 to n - m
    for v, pat in CHAINED-HASH-SEARCH'(T, hash(t_s))
      if v == t_s 
        if pat[1 : m] == T[s + 1 : s + m]
          print "Pattern " pat " occur with shifts" s
    if s < n - m
      t_{s + 1} = (d * (t_s - T[s + 1] * h) + T[s + m + 1]) mod q

对于模式串不等长的情况下，不能够使用上述哈希表的情况，只能分别独立地进行查询。通过数组模拟各种查询情况，最终整个过程由程序RABIN-KARP-MATCHER''给出，其时间复杂度为\(O(km(v+n/q))\)，其中\(v\)是有效偏移的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
RABIN-KARP-MATCHER''(T, P, n, k, d, q)
  h = d^(m - 1) mod q
  let p[1 : k] be a new array by 0
  let T be a new hash-table.
  for j = 1 to k
    t0 = 0
    for i = 1 to |P[j]|
      p[j] = (d * p[j] + P[j, i]) mod q
      t0 = (d * t0 + T[i]) mod q
    for s = 0 to n - |P[j]|
      if p == t_s
        if P[j, 1 : |P[j]|] == T[s + 1 : s + m]
          print "Pattern " P[j] " occur with shifts" s
      if s < n - m
        t_{s + 1} = (d * (t_s - T[s + 1] * h) + T[s + m + 1]) mod q

32.2-3

这道题的本质思想是将二维的情况转化为一维。对于每相邻\(m\)行，我们先预处理出一个长度为\(n\)的数组\(U\)，然后再在数组\(U\)上处理一维的情况，注意处理一行\(U\)的情况时，不像RABIN-KARP-MATCHER那样以\(d\)作为进制，而是以\(d'=d^m\)来作为进制。和RABIN-KARP-MATCHER同样的是，判断一个字符矩阵对应的值\(t\)是否和\(p\)相同只需要\(O(1)\)的时间即可完成。

一共需要判断\((n-m+1)^2\)种情况，因此在最坏情况下，这个二维版本的算法将会达到\(O((n-m)+1^2 \cdot m^2)=O(n^4)\)。具体过程由RABIN-KARP-MATCHER-2D给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
RABIN-KARP-MATCHER-2D(T, P, n, m, d, q)
  ha = d ^ (m * (m-1)) mod q
  hr = d ^ (m-1) mod q
  d' = d ^ m mod q
  p = 0
  for j = 1 to m
    for i = 1 to m
      p = (d * p + P[i, j]) mod q
  let U[1 : n] be a new array by 0
  for j = 1 to n
    for i = 1 to m
      U[j] = (d * U[j] + T[i, j]) mod q
  for rs = 0 to n - m
    u0 = 0
    for j = 1 to m
      u0 = (d' * u0 + U[j]) mod q
    for cs = 0 to n - m
      if p == ts
        if P[1 : m,1 : m] == T[rs + 1:rs + m,cs + 1:cs + m]
          print "Pattern occurs with shift" (rs, cs)
      if cs < n - m
        u_{cs + 1} = (d' * (u_{cs} - U[cs + 1] * ha) + U[cs + m + 1]) mod q
    if rs < n - m
      for j = 1 to n
        U[j] = (d * (u[j] - T[rs + 1, j] * ha) + T[rs + m + 1, j]) mod q

32.2-4

考虑令\(\displaystyle{f(A,B,x)=\left(\sum_{i=0}^{n-1}(a_i-b_i)x^i\right)\bmod q}\)。

如果两个文件相同，那么也就是说\(\forall i\in[0,n),a_i=b_i\)均成立，那么此时任取\(x\in[0,q)\)，都必定有\(A(x)=B(x)\)。

否则，非零多项式\(f(A,B,x)\)的次数至多为\(n\)。由于\(q\)是一个质数，依照题目31.4-4的结论，方程\(f(A,B,x)=0\)最多有\(n\)个不同的根。由于\(x\)是从\([0,q)\)中选择的，因此任取\(x\in [0,q),f(A,B,x)=0\)的概率至多为\(\dfrac{n}{q}\)。由于\(q>10^3\cdot n\)，因此\(f(A,B,x)=0\)的概率不会超过\(10^{-3}\)，原结论成立。