算法导论 32.1 Exercises 答案 发表于 2023-10-08 分类于 算法导论 阅读次数: 本文字数: 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' 给出。 123456789NAIVE-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),因此可以在多项式时间复杂度内完成这个问题。