子串检索有着很广泛的应用，例如在文档软件中查找关键词，网站过滤敏感词，生物学家查找某种模式的基因组序列等等，很多人听说过著名的KMP算法，Boyer-Moore算法做到的更多，有迹象表明在某些情况下效率是前者的3-5倍，且实现起来更加简单，符合我简单高效的原则。

下面先抛开算法不谈，如果让你在ABCSAKDFFEHHJDDEFKLD中查找DDEFK，你会怎么做？

最直接的就是暴力检索法，挨个比较文本和模式的每个字符，成功就继续比较模式字符的下一个，否则将模式往右移动一位，继续上述过程，直到文本的结尾或者搜索成功，通常情况下效率还可以，因为对于大部分文档往往只需要比较模式中的一两个字符，就会有非匹配字符，因此模式可以快速的向右移动，整体运行时间接近线性。java示例代码为

而本文的主角BM算法可谓别出心裁，它从后往前匹配模式的每一个字符，看看BM算法是如何处理上面的例子的，我们用i表示文本的起始位置，j表示模式中待匹配字符的位置。

第一步，i=0，j=4，A与K匹配失败，没有必要再往前匹配，i往后移动4+1=5个字符，因为小于这个数字，A都会与模式中的某个字符重叠，而模式中没有这个字符，无论如何都会失败。

第二步，i=5，j=4，E与K匹配失败，i需要再次往后移动，这次需要移动几个字符呢，答案是2，这样会将模式中最右边的E与文本中E对齐，小于这个数，文本中E会与模式E右边的字符重叠，这些字符中没有E，因此不可能成功。

第三步，i=7，j=4，这次匹配成功了，j减一j=3，又成功了，j再减一j=2，又成功了，j再减一j=1，这次F与D没有匹配成功，这次i要移动多少呢，F在文本和模式中都出现了，但是模式中的F已经匹配过了，我们不想让i回退，只能让i简单的加1。

第四步，i=8，j=4，同样J和K匹配失败，且J不在模式字符串中，同第一步，我们将i移动4+1=5个字符。

第五步，i=13，k=4，当j=4…0时，每个字符都匹配成功，成功检索到模式，将i=13返回，或者将i的值存储起来继续往后搜索，如果想得到模式的所有位置。

这样i移动5次，总共比较了12个字符，就完成了查找。

总结一下，BM算法的策略是从后往前匹配模式中的每个字符，直到文本中出现一个不匹配的字符txt.charAt(i+j)或者检索成功返回i。与暴力检索不同的是，当匹配失败时，BM算法不会按部就班的移动i，它首先会构造一个right数组，数组中存储的是字符集中每个字符在模式中最右边的位置，如果字符不在模式中设为-1，比如上面的例子，