算法导论32.1 Exercises 答案

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

32.1-1

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

\(\begin{array}{|c|l|c|c|}\hline s&\mathtt{000010001010001} &t(s)&\text{is matched}\\\hline 0&\mathtt{0001}&4&\text{No}\\\hline 1&\mathtt{\ 0001}&4&\text{Yes}\\\hline 2&\mathtt{\ \ 0001}&3&\text{No}\\\hline 3&\mathtt{\ \ \ 0001}&2&\text{No}\\\hline 4&\mathtt{\ \ \ \ 0001}&1&\text{No}\\\hline 5&\mathtt{\ \ \ \ \ 0001}&4&\text{Yes}\\\hline 6&\mathtt{\ \ \ \ \ \ 0001}&3&\text{No}\\\hline 7&\mathtt{\ \ \ \ \ \ \ 0001}&2&\text{No}\\\hline 8&\mathtt{\ \ \ \ \ \ \ \ 0001}&1&\text{No}\\\hline 9&\mathtt{\ \ \ \ \ \ \ \ \ 0001}&2&\text{No}\\\hline 10&\mathtt{\ \ \ \ \ \ \ \ \ \ 0001}&1&\text{No}\\\hline 11&\mathtt{\ \ \ \ \ \ \ \ \ \ \ 0001}&4&\text{Yes}\\\hline \end{array}\)

32.1-2

如果\(P\)的各个字母都不相同，那么可以考虑从左到右遍历文本串\(T\)，考察\(T\)中和\(P[1]\)相同的那些下标。由于\(P\)中的字符各不相同，因此对于一对相邻都是字符\(P[1]\)的下标\(i,j(i<j)\)，只有\(i+|P|\le 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)}\)。

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

令随机变量\(\displaystyle{Y=\sum_{s=0}^{n-m}\sum_{j=1}^{m}X_{ij}}\)表示比较次数，那么有：

\(\begin{aligned} E[Y]&=\sum_{s=0}^{n-m}\sum_{j=1}^{m}E[X_{ij}]\\ &=\sum_{s=0}^{n-m}\sum_{j=1}^{m}\dfrac{1}{d^{j-1}}\\ &=\sum_{s=0}^{n-m}\dfrac{d-d^{1-m}}{d-1}\\ &=(n-m+1)\cdot\dfrac{d-d^{1-m}}{d-1}\\ &=(n-m+1)\cdot\dfrac{1-d^{m}}{1-d^{-1}}\\ &\le(n-m+1)\cdot\dfrac{1}{1-d^{-1}}\\ &\le(n-m+1)\cdot\dfrac{1}{1-2^{-1}}\\ &\le2(n-m+1) \end{aligned}\)

32.1-4

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

\(f(i,j)= \left \{\begin{aligned} &1 & & \text{if}\quad i=0\land j=0 \\ &0 & & \text{if}\quad i=0\land j>0\lor i>0\land j=0\land P[i]\neq\Diamond\land f(i-1,0)=0 \\ &\bigvee_{k=0}^j f(i-1,k) & & \text{if}\quad i>0\land P[i]=\Diamond\\ &f(i-1,j-1)\land \mathbf{1}\{P[i]=S[j]\} & & \text{if}\quad i>0\land j>0\land P[i]\neq\Diamond\\ \end{aligned}\right.\)

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

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

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