算法导论32.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 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}$，原结论成立。