算法导论 32.1 Exercises 答案

32.1-1

t(s)(snm) 表示偏移为 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+j1]=P[1:j1],这个概率值为 d(j1)

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

令随机变量 Y=s=0nmj=1mXij 表示比较次数,那么有:

E[Y]=s=0nmj=1mE[Xij]=s=0nmj=1m1dj1=s=0nmdd1md1=(nm+1)dd1md1=(nm+1)1dm1d1(nm+1)11d1(nm+1)11212(nm+1)

32.1-4

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

f(i,j)={1ifi=0j=00ifi=0j>0i>0j=0P[i]f(i1,0)=0k=0jf(i1,k)ifi>0P[i]=f(i1,j1)1{P[i]=S[j]}ifi>0j>0P[i]

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

最终答案为 f(m,n)

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