BM

Algorithm
String
BM介绍

KMP算法是一种利用模式串前缀移动的字符串匹配算法，时间复杂度为O(n)。
BM算法是一种使用了两个跳转表的字符串匹配算法，单模式匹配有更加出色的表现。

上图表述了BM算法的大致过程，模式串是AT-THAT，于KMP不同，BM算法对每一次匹配尝试从后向前匹配的方法。

  1. 第一次匹配从第7位开始。第7为不能匹配，移动模式串，注意到目标串第7为为F，F不在模式串中，所以可以直接将模式串的首位移到目标串第8位。

  2. 接着从后向前匹配，目标串的14位-与模式串最后一位不匹配，但是-在模式串中，所以将模式串中最靠后的-移到与目标串的14位对齐。

  3. 再从后向前匹配，目标串的第18位T与模式串的最后一位匹配，向前看一位，17位L不匹配，且L不在模式串中，所以把模式串第一位移到目标串第18位。

  4. 接着从后向前匹配，第23、24位匹配，22位不匹配，由于模式串的前两位等于后两位，所以将模式串移动使其前两位到后两位的位置上。

坏字符规则

假设目标串T长度为n，模式串P长度为m

坏字符规则分为两种情况：

  • 坏字符没出现在模式串中，这时可以把模式串首移动到坏字符的下一个字符
  • 坏字符出现在模式串中，这时可以把模式串第一个出现的坏字符和母串的坏字符对齐（当然，这样可能造成模式串倒退移动）

使用一个数组bad，bad['k']表示坏字符在模式串中最左侧的字符'k'距离模式串末尾的长度，如果字符’k’不在模式串中，bad['k']=m。那么遇到坏字符时模式串可以移动的距离为：bad[T[i]]-(m-1-i).

1
2
3
4
5
6
7
// m为模式串长度
void get_bad (const char* P, int m, int* bad) {
    for (int i=0; i<256; i++)
         bad[i] = m;
    for (int i=0; i<m; i++)
        bad[P[i]] = m-i-1;
}
好后缀规则

发现某个字符不匹配的同时，已有部分字符匹配成功。假设模式串P已经匹配成功的部分为Q

  • 模式串中有子串匹配上好后缀，此时移动模式串，让该子串和好后缀对齐即可，如果超过一个子串匹配上好后缀，则选择最靠左边的子串对齐
  • 模式串中没有子串匹配上好后缀，此时需要寻找模式串的一个最长前缀，并让该前缀等于好后缀的后缀，寻找到该前缀后，让该前缀和好后缀对齐即可
  • 模式串中没有子串匹配上后后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀。此时，直接移动模式到好后缀的下一个字符

为了实现好后缀规则，需要定义一个数组suffix[]，其中suffix[i] = s 表示以i为右边界，与模式串后缀匹配的最大长度为s，即P[i-s:s]==P[m-s:m]，

1
2
3
4
5
6
7
8
9
void suffixes(const char *P, int m, int *suff) {
    suff[m-1]=m;
        for (i=m-2；i>=0；--i){
            q=i;
            while(q>=0&&P[q]==P[m-1-i+q])
                --q;
            suff[i]=i-q;
    }
}

定义good[]数组表示遇到好后缀时，模式串应该移动的距离。其中i表示好后缀前面一个字符的位置（也就是坏字符的位置）.对应上面三种情况，good数组构建方法如下：

上面的三种情况，移动的距离是逐渐增大的，在满足不止一种情况时，应该移动最小的距离。所以分三部分考虑，

  • 对第三种情况，移动距离就是P的长度
  • 对第二种情况，我们要找前缀，所以如果位置i到第一个是满足条件的话，必然有suff[i]=i+1，满足条件时，坏字符出现在[0,m-1-i)位置上时都可以移动m-1-i位使得模式串前i+1位与后i+1位重叠。对于i，从大到小计算是因为越长的前缀意味着越小的移动步数，我们希望找到小的，更新时判断good[j]==m也是为了不多次更新。
  • 对第一种情况，我们知道当m-1-suff[i]位置为坏字符时，需要移动m-i-1位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void get_good(const char *P, int m, int bmGs[]) {
    int i, j, suff[256];
    suffixes(x, m, suff);
    // 第三种情况
    for (i = 0; i < m; ++i)
        good[i] = m;
    j = 0;
    // 第二种情况
    for (i = m - 1; i >= 0; --i)
        if (suff[i] == i + 1)
            for (; j < m - 1 - i; ++j)
            if (good[j] == m)
                good[j] = m - 1 - i;
     // 第一种情况
     for (i = 0; i <= m - 2; ++i)
          good[m - 1 - suff[i]] = m - 1 - i;
}

最后给出BM算法，对于出现无法匹配的时候，移动步数取好后缀和坏字符两种情况的最大值。完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void BM(char *P, int m, char *S, int n) {
    int i, j, good[m], bad[256], k=0;
 
    /* Preprocessing */
    get_bad(P, m, bad);
    get_good(P, m, good);
    i = j = m-1;
    /* Searching */
    j = 0;
    while (j <= n - m) {
        while (i!=0 && P[i]==S[j]) {  // 从后向前匹配、直到找到不匹配或者完全匹配
            --i;
            --j;
        }
        // 找到一个匹配
        if (i==0 && P[i]==S[j]) {
            m++;
            j += good[0];  // 找到匹配算是好后缀情况
        } else {
            j += good[i]>bad[S[j]] ? good[i] : bad[S[j]];
        }
        i = m-1;
   }
}

分享到