字符串匹配——逆向思维BMH

BMH算法

BMH(Boyer-Moore-Horspool)算法是BM(Boyer-Moore)算法的一种优化，P从最右边开始比较。
核心：焦点在于坏字符上，根据字符在模式串P中出现的最后的位置算出偏移长度，偏移模式串的长度。

坏字符偏移表

在预处理中，计算大小为|∑|的偏移表。
设m为P串的长度：

字符在P模式串中： bmBc[char] = m-1-max （max为字符在P的最大位置，对于P串最后一个字符，若此前出现过则保留原值，否则偏移值为m）

字符不在P模式串中： bmBc[char] = m

例如：
P = “GTTAC” ，m = 5
bmBc[T] = 5 - 1 - max(T的位置) = 5 - 1 - 2 = 2
bmBc[C] = 5（C只在最后一个位置出现过，所以直接取长度m）
bmBc[U] = 5（U ∉ P）

计算可知偏移表如下：

P为短串（模式串），T为长串（目标串）

1. a中短串从‘C’往左比较，在长串‘T’字符位置失配，此时应从长串里已完成匹配的子串中找到最右端字符，本例为‘C’，查表可知C的偏移量为5，短串右移五格。
2. b图中首字符失配，且U在短串未出现过，短串右移五格。
3. c图长串首字符‘T’失配，T的偏移量为2，短串右移两格。
4. 最后一轮正好完全匹配。
   

   #include<bits/stdc++.h>
   #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   using namespace std;
   const int maxchar = 256; 
   void preBMH(const char* patt, int m, int bmBc[]) {
   int k = 0;
   for (k = 0; k < maxchar; k++) 
   bmBc[k] = m;
   /*m-1是为了考虑最后的字符在之前是否已有的情况，
   若没有则直接继承上面循环的m，若有就在本次循环更新*/ 
   for (k = 0; k < m-1; k++)
   bmBc[patt[k]] = m-k-1;
   }
   int BMH (string p, string t) {
   int m = p.length();
   int n = t.length();
   if (m > n) {
   cout << "find fail" <<endl;
   return -1;
   }
   int bmBc[maxchar];
   const char* patt = p.c_str();
   const char* text = t.c_str();
   preBMH(patt, m, bmBc);
   //定在P的最后一个字符 
   int k = m-1;
   while (k < n) {
   //j为p串，i为目标串 
   int j = m-1;
   int i = k;
   //从最右向左比较 
   while (j >= 0 && text[i] == patt[j]) {
     j--;
     i--;
   }
   //P全部匹配时i+1才为P的首字符index 
   if (j == -1) 
     return i+1; 
   //偏移量看的是目标串已完成匹配的子串中最右端字符！！
   k += bmBc[text[k]]; 
   }
   }
   int main() {
   fio
   string t = "GCCTCATCCUACGTTAC";
   string p = "GTTAC";
   int ans = BMH(p, t);
   cout << ans << endl; 
   }