算法——Boyer–Moore–Horspool algorithm（翻译版）算法,字符串,c++刘小白的博客-

舍卒保车，壮士断腕。（描述时空权衡） 

题目描述

Boyer-Moore字符串搜索算法是一种高效的字符串搜索算法.它是由鲍勃·博耶和J·斯特罗瑟·摩尔于1977年开发的。该算法预处理正在搜索的目标字符串(键)，但不预处理要搜索的字符串(与某些算法不同，这些算法预处理要搜索的字符串，然后可以通过反复搜索来摊销预处理的开销)。Boyer-Moore算法的执行时间实际上可以是次线性的：它不需要实际检查要搜索的字符串的每个字符，而是跳过其中的一些字符。通常，当搜索的密钥变得更长时，算法会变得更快。它的效率源于这样一个事实，即每次试图在搜索字符串和它正在搜索的文本之间找到匹配项时，它都会使用从该尝试中获得的信息来排除字符串无法匹配的文本中尽可能多的位置。

 算法是如何工作的：

当人们第一次遇到Boyer-Moore算法时，人们经常会感到惊讶的是，它的验证–它试图检查某个特定位置是否存在匹配–向后工作。例如，如果它在文本开头开始搜索“Anpanman”一词，它会检查文本的第八个位置，看看它是否包含“N”。如果它找到了“N”，它会移动到第七个位置，看它是否包含单词的最后一个“A”，等等，直到它检查文本的第一个位置是否为“A”为止。当我们考虑如果验证失败时，Boyer-Moore采取这种反向方法的原因更清楚–例如，如果我们在第八位没有找到“N”，而是找到了一个“X”。“X”没有出现在“Anpanman”中的任何地方，这意味着在文本的开头–或者后面的七个位置–没有匹配的搜索字符串，因为所有这些都会落在“X”之间。在“X”之后。这解释了为什么对于长度为N的文本和长度为M的固定模式，该算法的最佳情况性能是N/M：在最好的情况下，只需要检查M字符中的一个。这也解释了在某种程度上违背直觉的结果，即我们寻找的模式越长，算法通常就能越快地找到它。该算法预计算两个表，以处理在每个失败验证中获得的信息：一个表根据导致匹配尝试失败的字符的标识计算前面的几个位置，以启动下一个搜索；另一个表根据尝试匹配失败之前成功匹配的字符数进行类似计算(因为这两个表返回的结果表明在文本中“跳转”有多远，所以它们有时被称为“跳转表”，这不应与计算机科学中跳转表更常见的含义混淆。)。

第一个表：

第一个表很容易计算：从查找字符串的最后一个字符开始，然后移动到第一个字符。每次向左移动时，如果您所在的字符不在表中，则添加它；它的移位值是它与最右边字符之间的距离。所有其他字符都会收到与搜索字符串长度相等的计数。

 例子：

对于字符串Anpanman，第一个表将如图所示(为了清晰起见，条目按添加到表中的顺序显示)：(假定为零的N基于右边的第二个N，因为我们只从字母m-1计算)。

 第一个表计算的移位量有时被称为“坏字符移位”[1]。

第二个表：

第二个表更难计算：对于小于搜索字符串长度的每个i值，我们必须首先计算由搜索字符串的最后i个字符组成的模式，前面是对前面字符的错误匹配；然后我们首先将其与搜索模式对齐，并确定两个模式匹配之前必须左移的部分模式必须移动的最少字符数。例如，对于搜索字符串Anpanman，表如下所示：(n表示任何不是N的字符)

 第二个表计算的移位量有时称为“好后缀移位”[2]或“(强)好后缀规则”。最初出版的Boyer-Moor算法[1]使用了更简单、更弱的好后缀规则，其中上表中的每个条目都不需要对最左边的字符进行错误匹配。这有时被称为“弱好后缀规则”，不足以证明Boyer-Moore在线性最坏情况下运行。

Boyer-Moore字符串搜索算法的性能：

在最坏的情况下，要查找文本中的所有事件，需要进行大约3*N的比较，因此，无论文本是否包含匹配项，复杂度都是O(N)。这一证明应归功于Richard Cole，见R.Cole，关于Boyer-Moore算法复杂性的严格限制，第二届ACM-SIAM离散算法研讨会会议记录(1991)。这个证据花了几年时间才确定。在该算法设计的那一年，1977年，最大的比较次数显示不超过6*N；在1980年，它被证明不超过4*N，直到1991年Cole的结果。

输入

字符串中只有两行字符“ACGT”。第一行是字符串(<=102000)，第二行是文本(<=700000)

输出

字符串在文本中的位置否则输出-1

样例输入

GGCCTCATATCTCTCT
CCCATTGGCCTCATATCTCTCTCCCTCCCTCCCCTGCCCAGGCTGCTTGGCATGG

 样例输出

6

题目链接 

解题

看到字超级多的题目不要慌，因为大部分都没有我们想象的那么难，比如本题，大量的字数只是为了解释 Boyer-Moore-Horspool 算法的知识点，而本题真正要求的是在字符串匹配中，利用Boyer-Moore-Horspool算法，找出字符串在文本中的位置，未找到匹配项，则输出-1.

本题的题目描述即Boyer-Moore-Horspool算法的描述，所以我把全文翻译出来（现在网上翻译技术很赞），以便读者理解。

Horspool算法：

第一步：对于给定的长度为len_str的模式和在模式及文本中用到的字母表，构造移动表；

第二步：将模式和文本的开始对齐；

第三步：重复下面的过程，直到发现了一个匹配子串或者模式到达了文本的最后一个字符以外。从模式的最后一个字符开始，比较模式和文本的相应字符，直到：要么所有len_str个字符都匹配（然后停止），要么遇到了一对不匹配的字符。在后一种情况下，如果c是当前文本中和模式的最后一个字符相对齐的字符，在从移动表的第c列中取出单元格 t(c) 的值，然后将模式沿着文本向右移动 t(c) 个字符的距离。

完整代码

 #include<iostream> #include<cstring> using namespace std; int table[26]; int horspoolMatch(char str[],char text[]){  int len_str = strlen(str);  int len_text = strlen(text);  for(int i = 0; i < len_str - 1; i ++){   table[str[i] - 'A'] = len_str - i - 1;   }  int p = len_str - 1;  while(p < len_text){   int k = 0;   while(str[len_str - 1 - k] == text[p - k] && k <= len_str){    k++;   }   if(k == len_str){    return p - len_str + 1;   }   else p += table[text[p] - 'A'];  }  return -1; } int main(){  char str[102000],text[700000];  cin>>str>>text;  cout<<horspoolMatch( str, text)<<endl;  return 0; }

上几篇算法：

• 算法——简单背包问题
• 算法——Coin Changing（最少硬币数）