
_START_ARTICLE_
Boyer-Moore字符串搜索算法
_START_PARAGRAPH_
在计算机科学里，Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串（关键字）进行预处理，而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。
_START_SECTION_
原理
_START_PARAGRAPH_
不同于朴素模式（brute-force search）的逐个字符对比，Boyer-Moore充分使用预处理P的信息来尽可能跳过更多的字符。通常，我们比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较。这样，就需要将字符串中的所有字符一一比较。Boyer-Moore算法的关键在于，当P的最后一个字符被比较完成后，我们可以决定跳过一个或更多个字符。如果最后一个字符不匹配，那么就没必要继续比较前一个字符。如果最后一个字符未在P中出现，那么我们可以直接跳过T的n个字符，比较接下来的n个字符，n为P的长度（见定义）。如果最后一个字符出现在P中，那么跳过的字符数需要进行计算（也就是将P整体往后移），然后继续前面的步骤来比较。通过这种字符的移动方式来代替逐个比较是这个算法如此高效的关键所在。_NEWLINE_形式化的表述方式为，从k=n开始，也就是P从T的最开始进行比较。紧接着，P的第n个字符和T的第k个字符开始：字符串依次从P的最后一个字符到最开始的字符。结束条件是当比较到达P的最开始（此时匹配完成），或按照规则移动后的字符部匹配发生时。然后，在新的对齐位置重新开始比较，如此反复，直到到达T的结尾。_NEWLINE_移动规则是一张间恒定的查找表，通过对P的预处理产生的。
_START_SECTION_
移动规则
_START_PARAGRAPH_
移动字符数是通过两条规则决定的：坏字符规则和好后缀规则。实际移动为通过这两条规则计算出的最大移动个数。
_START_SECTION_
处理
_START_PARAGRAPH_
当我们发现不匹配字符时，假设这个字符在T中为c，位置在T的i。字符c在P中出现的最靠近i位置，假设为j，j<i或j=-1（如果P不存在字符c）。那么移动位数为i - j，复杂度是O(1)。i，j的起点为P在T中位置的开始T[(k-n+1)..k]的(k-n+1)。_NEWLINE_大多网站都只创建一个一维坏字符数组来保存，但事实这只能保存最靠左或最靠右的字符c，明显与英文的wikipedia里面要求一个二维数组来保存信息的不一样。
_START_SECTION_
原理
_START_PARAGRAPH_
好后缀规则要更复杂一点。_NEWLINE_假设有P和T，T中字符串t匹配到了P的一个后缀，但在比较位置i时发生不匹配。设匹配到的好后缀在T中为t，在P中为t'（t = t'）。_NEWLINE_分两种情况来讨论：_NEWLINE_1，在P中i位置的左侧最靠近i位置查找字符串t'使得t'=t（此时t'不是P的后缀，实际上也就是查找匹配到的字符串除了在P的后缀中存在，是否在P的其他位置存在），若存在，则移动相应的位数将找到的t'与T中的t对齐。_NEWLINE_2，如果t'不存在，那我们继续查找t的某一个后缀是否为P的前缀，若存在，则移动相应的位将P的前缀与t的后缀位置对齐。否则，将P向后移动n个字符。_NEWLINE_好后缀规则的实质是，将不匹配位置右侧匹配到的字符串t的所有字符后缀组合，用于查找它们在P的不匹配位置左侧是否存在。_NEWLINE_通俗的理解是，最长的好后缀t是否存在于i的左侧（情况1），其他后缀组合中是否存在与P的前缀相同的情况（情况2）。
_START_SECTION_
举例
_START_PARAGRAPH_
假设被检索文字列是“1234567890”，检索文字列是“MOORE”。简单的比较需要执行十次才得到结论不匹配。被检索文字列：1234567890_NEWLINE_  第一次比较：M....         （M和1比较，不匹配）_NEWLINE_  第二次比较：M....        （M和2比较，不匹配）_NEWLINE_  第三次比较：  M....       （M和3比较，不匹配）_NEWLINE_        ..._NEWLINE_  第十次比较：         M....（M和0比较，不匹配）_NEWLINE_※未参与比较的文字用【.】占位。_NEWLINE_BM算法只需要2次比较。_NEWLINE_被检索文字列：1234567890_NEWLINE_  第一次比较：....E        （E和5比较，不匹配，并且5不是MOORE中任何文字）_NEWLINE_  第二次比较：     ....E   （E和0比较，不匹配，并且0不是MOORE中任何文字）_NEWLINE_第一次从检索文字的末尾开始，因为如果被检索文字的第5文字位置不是E，则无论前4个文字是什么，都绝不可能匹配了。这一点比较容易理解。_NEWLINE_那么，为什么不用E和6比较呢？_NEWLINE_这是BM算法又一处精妙之处。在E和5进行比较的时候不仅知道他们不相等，而且还知道了5不和检索文字MOORE中的任何一个文字相等，这使得下面这些比较都可以省略掉。_NEWLINE_被检索文字列：....5......_NEWLINE_不需要的比较：...R.       （E和5比较时也同时发现5不等于R，于是这个比较是不必要的）_NEWLINE_不需要的比较：  ..O..      （E和5比较时也同时发现5不等于O，于是这个比较是不必要的）_NEWLINE_不需要的比较：   .O...     （E和5比较时也同时发现5不等于O，于是这个比较是不必要的）_NEWLINE_不需要的比较：    M....    （E和5比较时也同时发现5不等于M，于是这个比较是不必要的）