BoyermooreAlgorithm.docVIP

Boyer-Moore字符串有哪些信誉好的足球投注网站算法是一种非常高效的字符串有哪些信誉好的足球投注网站算法。它由Bob Boyer和J Strother Moore设计于1977年，最初定义1975年就给出了基本定义，后续才给出构造算法以及算法证明。 BM算法较KMP 算法效率要高，同时也更复杂； 主要区别： 1、KMP 从左向右比较，而BM算法从右向左比较; 2、BM算法有两个跳转规则，KMP只有一个; 先假设部分定义： 1、pattern 为模式字符串，长度为patLen; 2、Text为目标查找字符串，长度为n; 2、当前不匹配字符在pattern中位置为 j（0≤ j ≤patLen -1）; 3、已经匹配的长度为 m（0≤ m ＜patLen）; 4、先假设不匹配字符在pattern中位置为 Δ(*),其中*可以是任何字符; 很多资料里面讲解原理时说的数组位置都是从1开始的，这里为了好理解code，都是从0开始; 首先来看下坏字符规则： 一、坏字符规则（bad character rule ）：让不匹配字符和pattern中最右边出现的该字符对齐匹配，如果没有则全部跳过； 假设1：遇到不匹配字符，如果该字符在pattern 中不存在，有:（如下图示跳转） 字符指针右移：patLen 长度 后和 pattern 右对齐; Pattern 右移：patLen – m; 假设2：遇到不匹配字符，如果该字符在pattern 中存在，这里也分两种情况: a在pattern最右边出现的该字符在当前不匹配字符左边，有:（如下图示跳转） 字符指针右移：j–Δ(‘-’) +m = (j + m)–Δ(‘-’) = (patlen – 1) -Δ(‘-’) = (7-1)-2 = 4 Pattern 右移：字符指针偏移 - m = 4 – m = 2; b在pattern中最右边出现的该字符在当前不匹配字符右边, 有:（如下图示跳转） 字符指针右移: (patlen-1) – Δ(‘T’) = (7-1) – 6 = 0 Pattern右移：字符指针偏移 – m = 0 – 2 = -2 可以看出，pattern 竟然回退比较了，这是不应该出现的，这时候直接往后移动1位就行了： 总结上面三种情况,我们定义坏字符函数delta1() 为字符指针的偏移： Delta1($) = patLen;(不匹配字符在pattern中不存在) = patLen – 1 -Δ(*);(不匹配字符在pattern中存在，且在pattern中最右边出现的该字符在当前不匹配字符左边) = 1;( 不匹配字符在pattern中存在，且在pattern中最右边出现的该字符在当前不匹配字符右边) 二、好后缀规则（good suffix rule）：根据已经匹配的部分字串(subpat)，在pattern中寻找是否有和 subpat 全部或者部分匹配的字串，直接对齐匹配，避免无效的移动； 介绍好后缀规则前先约定几点： 1、 假设 $ 为pattern中没有出现过的字符，有pat[i] = $ 当i 0; 2、 两个序列[C1 … Cn] 和[d1… dn] 是一致的, 当且仅且cj = dj 或者 cj = $ 或者 dj = $；其中(0≤j＜n) 3、 最右边可能重新出现的subpat 的位置为rpr(j), 是使[pat[j + 1] ... pat[patlen]] 和 [pat[k] ... pat[k + patlen - j – 1] ]一致的最大K值，其中k≤0 或者pat[k – 1] != pat[j]. 上图写出了pattern “ABXYCDEXY” 的rpr()值计算结果：我们来解析下： a.当j = 8 时，已经匹配字串p[j+1 … patLen-1] 为空，参照rpr()定义，可知，pattern最右边可能和空串一致的，就是p[8 ~ PatLen-1], 可知rpr(8) = 8. b.当j = 7时，已经匹配字串subpat为”Y”, 可以看到p[3 ~ 3] = subpat , 但是此时k=30, 同时pat(k-1) == pat[j] = “X”, 所以表明该subpat只可能存在pattern头部-1位置，即rpr(7) = -1. c.当i = 6 时，已经匹配字串subpat为”XY”, 可以看到p[2 ~ 3] = subpat, 同时满足p[k-1] != pat[j] ,可知rpr(6) = 2. d.当I = 5 时，已经匹配字串subpat为”EXY”, pattern中没有对应字串和subpat一致，只可能存在pattern头部，可知rpr(5) = -3; 其他情况依次类推，上面的几种情况应该包含了所有