对“坏字符情况的预处理 算法: 对于这种情况,我们首先定义一 fora←0 to alphabets 的每一个字符在模式串中出现的最右 置,如果根本没有出现在模式串中 forj·otom 定义 j|p,=a}如果a出现在模式串中 如果a没有在模式串中出现 occa 例子: 其中p0P1pm代表模式串,a是广义字母 occ(text, x)=2 表中的任一字符。 occ(text, t)=3 对“好后缀”情况的预处理 对“好后缀”情况的预处理 第一种情形:已匹配的后缀子串在模式串的 其它位置又出现。 我们也要建立一个数组s。数组里的 第项代表不匹配发生在模式串的位置i-1 (即模式串位置i始的后缀已和目标串 相应子串匹配)时模式串应当右移的位 01234567 然后再建立一个数组f。第项代表模 a b aa b 式串中从位置开始的后缀其最长边界开 ipfs 56456778 始的位置 00002041 对“好后缀”情况的预处理 bmPreprocessl () BM预处理算法 第二种情形:已匹配的后缀子串仅仅有一部 分又出现在模式串的开头。 do while j<=m and p[i-l*pl-I] BM检紫算法 hile j=o and pD=at(l+il 例子::01234567 bmPreprocess20 p f:56456778 0cb5 e i-i+max闻s s:55552541 then+fDl8 43 对“坏字符”情况的预处理 对于这种情况，我们首先定义一个函数occ 生成一个数组，在这个数组中记录广义字母表 的每一个字符在模式串中出现的最右边的位 置，如果根本没有出现在模式串中，则记-1。 定义： 其中p0 p1…pm -1代表模式串，a是广义字母 表中的任一字符。 -1 a max{ j | p = a} a occ(p,a) = j ⎪⎩ ⎪ ⎨ ⎧ 如果 没有在模式串中出现 如果 出现在模式串中 44 算法： bmInitocc() for a ← 0 to alphabetsize do occ[a] ← -1 for j ← 0 to m do a ← p[j] occ[a] ← j 例子： occ(text, x) = 2 occ(text, t) = 3 45 对“好后缀”情况的预处理 我们也要建立一个数组s。数组里的 第i项代表不匹配发生在模式串的位置i-1 （即模式串位置i开始的后缀已和目标串 相应子串匹配）时模式串应当右移的位 数。 然后再建立一个数组f。第i项代表模 式串中从位置i开始的后缀其最长边界开 始的位置。 46 对“好后缀”情况的预处理 第一种情形：已匹配的后缀子串在模式串的 其它位置又出现。 i: 0 1 2 3 4 5 6 7 p: a b b a b a b f: 5 6 4 5 6 7 7 8 s: 0 0 0 0 2 0 4 1 47 对“好后缀”情况的预处理 第二种情形：已匹配的后缀子串仅仅有一部 分又出现在模式串的开头 。 例子：i: 0 1 2 3 4 5 6 7 p: a b b a b a b f: 5 6 4 5 6 7 7 8 s: 5 5 5 5 2 5 4 1 48 bmPreprocess1（） i ← m j ← m+1 f[i] ← j while i>0 do while j<=m and p[i-1]≠p[j-1] do if s[j]=0 then s[j] ← j-1 j ← f[j] i ← i-1 j ← j-1 f[i]=j bmPreprocess2() j ← f[0] for i ← 0 to m do if s[i]=0 then s[i] ← j if i=j then j ← f[j] BM预处理算法 bmPreprocess() call bmInitocc() call bmPreprocess1() call bmPreprocess2() BM检索算法 bmSearch() i ← 0 while i<=n-m do j ← m-1 while j>=0 and p[j]==t[I+j] do j ← j-1 if j<0 then return i i ← i+s[0] else i ← i+max(s[j+1],j￾occ[t[i+j]])