坏字符规则

January 30, 2023

Content #

BM 算法的匹配顺序是按照模式串下标从大到小的顺序，倒着匹配的。

从模式串的末尾往前倒着匹配，当发现某个字符没法匹配的时候，把这个没有匹配的字符叫作坏字符（主串中的字符）。

拿坏字符 c 在模式串中查找，发现模式串中并不存在这个字符时，可以将模式串直接往后滑动三位，从模式串的末尾字符开始比较。

这个时候，坏字符 a 在模式串中是存在的，模式串中的 a 的下标是 0。此时，不能滑动三位，模式串应往后滑动两位，让两个 a 上下对齐，然后再从模式串的末尾字符开始，重新匹配。

第一次不匹配的时候，滑动了三位，第二次不匹配的时候，将模式串后移两位，那具体滑动多少位，到底有没有规律呢？

当发生不匹配的时候，把坏字符对应的模式串中的字符下标记作 si。如果坏字符在模式串中存在，把这个坏字符在模式串中的下标记作 xi。如果不存在，把 xi 记作 -1。那模式串往后移动的位数就等于 si-xi。（注意，这里说的下标，都是字符在模式串的下标）。

如果坏字符在模式串里多处出现，那在计算 xi 的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情况被滑动略过。

利用坏字符规则，BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)。比如，主串是 aaabaaabaaabaaab，模式串是 aaaa。每次比对，模式串都可以直接后移四位，所以，匹配具有类似特点的模式串和主串的时候，BM 算法非常高效。

不过，单纯使用坏字符规则还是不够的。因为根据 si-xi 计算出来的移动位数，有可能是负数，比如主串是 aaaaaaaaaaaaaaaa，模式串是 baaa。不但不会向后滑动模式串，还有可能倒退。所以，BM 算法还需要用到“好后缀规则”。