字符串匹配的Boyer-Moore算法 字符串匹配是数据结构与算法中的经典问题，Boyer-Moore算法是其中效率最高的算法之一，尤其适用于文本串较长、模式串较短的场景。它的核心思想是通过预处理模式串，在匹配失败时跳过尽可能多的字符，从而减少比较次数。 1. 算法基本思想 Boyer-Moore算法从模式串的末尾开始向前匹配（即从右向左比较），并利用两种启发式规则决定匹配失败时的跳跃距离： 坏字符规则（Bad Character Rule） 好后缀规则（Good Suffix Rule） 算法每次尝试将模式串与文本串对齐，从模式串的最后一个字符开始比较。若发生不匹配，则根据两种规则计算跳跃距离，取较大值移动模式串。 2. 坏字符规则（Bad Character Rule） 步骤： 当模式串与文本串的某个字符不匹配时，称文本串中的这个字符为“坏字符”。 在模式串中从右向左查找坏字符最后一次出现的位置（若不存在则为-1）。 跳跃距离 = 坏字符在模式串中的位置索引 - 模式串中该字符最后一次出现的索引 。 若坏字符在模式串中不存在，则直接跳过整个模式串长度。 示例： 文本串： A B C D E F G H 模式串： C D E 第一次比较：比较 E 与 C （不匹配），坏字符是 C 。 模式串中 C 的位置索引为0，当前对齐下坏字符在文本串的索引为2（从0开始）。 跳跃距离 = 2 - 0 = 2（实际计算时需用模式串索引调整，详见预处理表）。 预处理坏字符表： 为模式串生成一个哈希表，记录每个字符在模式串中最后一次出现的位置（索引）。例如模式串 "ABCA" ： A 最后出现在索引3， B 在索引1， C 在索引2，其他字符为-1。 3. 好后缀规则（Good Suffix Rule） 步骤： 当匹配失败时，已匹配的后缀称为“好后缀”。 在模式串中查找与好后缀相同的子串： 若存在另一个与好后缀匹配的子串，将模式串移动到该子串与好后缀对齐。 若不存在，则找到好后缀的最长前缀，使其与模式串的某个后缀匹配。 示例： 文本串： A B C A B D A B C 模式串： A B D A B 对齐后比较： 后缀 A B 匹配，但 D 与 C 不匹配。 好后缀是 "AB" ，在模式串的前缀 "AB" （索引0~1）与好后缀匹配。 移动模式串使前缀 "AB" 与文本中的好后缀对齐。 预处理好后缀表： 构建数组 suffix 和 prefix ，记录模式串中每个后缀的出现位置及其是否为前缀。 4. 算法完整流程 预处理模式串，生成坏字符表和好后缀表。 将模式串与文本串左对齐，从模式串末尾开始比较。 若所有字符匹配，则记录匹配位置。 若出现不匹配： 计算坏字符规则下的跳跃距离 skip_bc 。 计算好后缀规则下的跳跃距离 skip_gs 。 模式串向右移动 max(skip_bc, skip_gs) 位。 重复直到模式串超出文本串范围。 5. 时间复杂度分析 最坏情况：O(mn)（如文本串 AAAA ，模式串 BAAA ），但实际应用中接近O(n/m)。 空间复杂度：O(m + k)（k为字符集大小）。 6. 示例演示 文本串： "HERE IS A SIMPLE EXAMPLE" 模式串： "EXAMPLE" 对齐末尾：比较 "E" 与空格（不匹配），坏字符为空格（不在模式串），直接移动7位。 对齐后继续比较，利用坏字符和好后缀规则跳跃，最终在索引17处找到匹配。 通过结合两种规则，Boyer-Moore算法显著减少了字符比较次数，成为实际应用中高效的字符串匹配算法。