串匹配二：Boyer-Moore算法

当我们在匹配时，如果从右向左扫描模式串并将它和文本匹配。

类似查找"BAABBAA"时，如果匹配了第5个字符和第6个字符。但在第4个字符处匹配失败，则可以将模式串向右移动7位，因为是XAA，而这个X不是B。
一般来说，模式串的结尾部分也可能出现在文本的其他位置，这种和KMP方法类似。

现在介绍Boyer和Moore给出的另一种从右向左扫描模式串更有效的方法。

启发式处理不匹配字符串

如图显示了在文本 F I N D I N A H A Y S T A C K N E E D L E 中查找模式串 N E E D L E的过程：

从右向左匹配，所以首先会比较 文本串中的N 和 模式串中的E。因为N也出现在模式串中，所以将模式串向右移动，使'N'对齐。

然后比较 文本串中的S 和 模式串中的E，因为S没有出现在模式串中，所以将模式串向右移动6位。

因为匹配到文本串中的N，所以将模式串向右移动4位，使'N'对齐。

启发式处理不匹配字符串.png

上面过程中，我们必须要知道每次对齐要移动的位数，所以现在使用数组right[ ]记录字母表中的每个字符在模式串中出现的最靠右的位置（如果字符在该模式串不存在则表示为-1）。

right [ ].png

匹配过程

我们用索引 i 在文本串中从左向右移动，用另一个索引 j 在模式串中从右向左匹配。
如果从M-1到0的所有j，txt[ i+j ] 和 pat[ j ]相等，则匹配成功，否则匹配失败。

• 造成匹配失败的字符不包含在模式串中

a.png

• 造成匹配失败的字符包含在模式字符串中
  就可以使用right[ ]数组将模式串和文本串对齐，使得该字符和它在模式串种出现的最右位置匹配。

b.png

• 造成匹配失败的字符包含在模式字符串中，但却会将模式串向左移动
  这种"对齐"之后，会将模式串向左移动。此时我们只有将i加1，使模式串向右移动

  
  c.png

实现

/* 以下代码只为实现启发式处理不匹配字符串核心思想，未考虑边界测试 */
int BMmatch(const std::string& txt, const std::string& pat)
{
    int N = txt.size();
    int M = pat.size();
    std::vector<int> right(256, -1);

    /* 构造right数组 */
    for (int i = 0; i != M; i++)
        right[pat[i]] = i;

    int skip;
    for (int i = 0; i <= N-M; i += skip) {
        skip = 0;
        for (int j = M-1; j >= 0; j--) {
            if (pat[i+j] != txt[j]) {
                skip = j - right[txt[i+j]];
                if (skip < 1)
                    skip = 1;
                break;
            }
        }
        if (skip == 0)
            return i;
    }

    return -1;
}