Boyer-Moore算法详解与应用

"BM算法，也称为Boyer-Moore算法，是一种高效的字符串搜索算法，由Robert S. Boyer和J Strother Moore在1977年提出。该算法通过利用坏字符规则和好后缀规则，能够在大部分情况下显著减少不必要的字符比较，从而提高搜索效率。" Boyer-Moore算法的核心在于其两个关键规则： 1. **坏字符规则**：在模式串（要查找的子串）与目标串（主字符串）的比较过程中，如果在模式串的末尾找到一个不匹配的字符c，算法会根据预先计算的坏字符表，确定模式串应移动的距离。坏字符表记录了每个字符在模式串中最后一次出现的位置。如果字符c不在模式串的其他位置出现，则模式串可以直接跳过整个目标串，即移动距离为模式串长度。否则，移动距离为模式串最后一个字符索引减去字符c的最后出现位置。 当不匹配的字符出现在已匹配的模式串部分时，坏字符规则可能无效，因为在这种情况下，模式串需要移动更多或更少的位数。在这种情况下，好后缀规则发挥作用。 2. **好后缀规则**：此规则利用了已匹配的后缀信息。如果在模式串的末尾找到一个不匹配的字符，算法会查找模式串中是否存在一个后缀，这个后缀在模式串中也出现在不匹配字符的左侧。如果有这样的后缀，模式串可以移动到目标串中这个后缀的下一个出现位置，以尝试再次匹配。如果后缀的前一个字符相同，算法会继续向左移动，直到找到一个不同的前一个字符，以避免再次失配。 好后缀规则的一个关键点是找到模式串的“合理重现”，即找到一个位置p，使得模式串的后缀从p+1开始与模式串的一部分匹配，但p位置上的字符不同。这允许模式串进一步跳跃，减少比较次数。 Boyer-Moore算法在最坏情况下的时间复杂度是O(nm)，其中n是目标串的长度，m是模式串的长度。然而，在实际应用中，由于这两个规则的存在，它通常比简单的逐字符比较算法更快。特别是在模式串较长而目标串较短，或者模式串中字符分布均匀的情况下，性能优势更为明显。