首先，请就BM算法的难度进行引导。 请大家冷静下来，咀嚼和阅读。 这样，你就能取得成果。
在文本编辑器中，搜索和替换功能非常常用。 例如，在Word文件中，搜索和替换功能允许一个单词被一起替换为另一个单词。 对于文本编辑器等软件来说，搜索和替换是其核心功能，他们希望使用尽可能高效的字符串匹配算法。 我以前研究过RK算法。 时间复杂度是o(n )，其实已经很有效率了。 现在介绍一种新的字符串匹配算法，一种拜尔模式(BM )算法。
BM算法的核心思想BM算法是一种非常高效的字符串匹配算法，但BM算法原理非常复杂，理解起来可能有点困难，大家花费半小时静下心去好好研究一下。
模式列与主列的匹配过程可以看作模式列在主列中不断向后滑动。 如果发现不匹配的字符，BF和RK算法将图案列向后滑动一位，使其与图案列中的第一个字符重新匹配。
主字符串中的字符c如果在模式列中没有对应的字符，就一定不一致。 因此，如下图所示，可以将图案列一次向后滑动几个数字，将图案列移动到字符c的后面。
其实，BM算法在寻找本质上存在的规律。 此规则允许您跳过图案列与主列匹配、图案列与主列中的字符不匹配、绝对不匹配的情况，并将图案列向后滑动几个数字。 这样可以提高字符串匹配的效率。
BM算法原理分析BM算法的具体实现原理包括两部分：坏字符规则(bad character rule)和好后缀规则(good suffix rule)。
1 .不良字符规则BF算法中模式串与主串的匹配按下标从小到大的顺序进行，按BM算法的匹配顺序却是比较特殊，他是按照模式串下标从大到小的顺序倒叙进行的。如下图。
请注意，从模式串的末尾往前倒着匹配，当发现某个字符无法匹配的时候，我们就把这个无法匹配的字符称为“坏”字符坏字符是指主字符串中的字符，而不是模式字符串中的字符。 如下图所示。
尝试使用坏字符c查找模式列时，发现模式列中不存在该字符。 也就是说，字符c与模式列中的任何字符都不匹配。 此时，可以将图案列直接滑动到字符c的后面，从图案列末尾的字符开始重新进行比较。
如果将图案列滑动到c，则可以看到图案列中的最后一个字符d仍然与主列中的字符a不匹配。 此时，是否可以使图案列滑动到主列中的坏字符a (主列中的第三个a )之后？
其实不行。 因为模式列中存在坏字符a。 也就是说，下标为0的位置存储的是字符a。 因此，可以将图案列向后滑动两位，使图案列中的a与主列中的第三个a上下对齐，然后从图案列的最后一个字符开始匹配。
现在可能会发现一个问题。 那是第一次我们移动模式列时，移动了3位，但第二次移动了2位。 那么，关于移动的具体次数，有规则性吗？
在模式列与主列不一致的情况下，将与坏字符对应的模式列中的字符在模式列中的下标记设为si。 图案列中存在不良字符时，图案列下方将不良字符标记为xi，图案列中不存在不良字符时，将xi标记为-1。 那么，图案列向后滑动的位数与si-xi相同。
另外，在图案列中多次出现不良字符的情况下，在计算xi时，选择图案列中最后面的哪个不良字符的下标作为xi的值。 这样，就不会因模式过于跳跃而忽视本来可能一致的情况。
使用不良字符规则，BM算法在最佳情况下的时间复杂度非常低，是o(n/m )。 例如，主字符串是aaabaabaaabaaaaab，模式列是aaaa。如果模式列与主字符串不匹配(坏字符是b )，则可以将模式列直接向后滑动4位，因此具有相似特征的主字符串和模式列
但是，仅仅使用不良的文字规则是不够的。 因为根据si-xi计算出的滑动位数还可能为负数。 例如，主字符串是aaaaaaaaaaaa，模式字符串是baaa。 对于这种情况，还需要另一条规则，好的后缀规则。
2 .好的后缀规则好的后缀规则和坏的文字规则很相似。 当图案列滑动到下图所示的位置时，图案列与主列匹配两个字符，倒数第三个字符不匹配。
看看后缀规则是如何工作的。
我们把已经一致的' bc '称为好的后缀，标记为{u}。 我们用他在图案列中查找，找到与好后缀{u}匹配的另一个子串{u*}，然后将图案列滑动到子串{u*}和好后缀{u}上下对齐的位置。 如下图所示。
如果找不到与图案列中的好后缀{u}匹配的其他子列，请将图案列直接滑动到好后缀{u}之后。
但是，你没想过这个问题吧？ 如果模式列中不存在与好的后缀{u}匹配的子列，则将模式列直接滑动到好的后缀{u}之后。 是不是有点过头了？ 请看下图的一个例子，' bc '是一个很好的后缀。 图案列中没有另一个子列与好的后缀匹配，但如果图案列移动到好的后缀之后，则会忽略图案列和主字符串的匹配
p> 如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中， 只要主串中的{u}与模式串有重合，那肯定就无法完全匹配。但是当模式串滑动到前缀与主 串中{u}的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配 的情况。所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还 要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。 所谓某个字符串 s 的后缀子串，就是最后一个字符跟 s 对齐的子串，比如 abc 的后缀子串 就包括 c, bc。所谓前缀子串，就是起始字符跟 s 对齐的子串，比如 abc 的前缀子串有 a， ab。我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设 BM是{v}，然后将模式串滑动到如图所示的位置。 当模式串和主串中的 某个字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来计算模式串往后滑动的 位数？ 我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往 后滑动的位数。这种处理方法还可以避免我们前面提到的，根据坏字符规则，计算得到的往 后滑动的位数，有可能是负数的情况。
BM算法的代码实现 “坏字符规则”本身不难理解。当遇到坏字符时，要计算往后移动的位数 si-xi，其中 xi 的 计算是重点，我们如何求得 xi 呢？或者说，如何查找坏字符在模式串中出现的位置呢？如果我们拿坏符在模式串中顺序遍历查找，这样就会比较低效，势必影响这个算法的性 能。有没有更加高效的方式呢？我们之前学的散列表，这里可以派上用场了。我们可以将模 式串中的每个字符及其下标都存到散列表中。这样就可以快速找到坏字符在模式串的位置下 标了。 关于这个散列表，我们只实现一种最简单的情况，假设字符串的字符集不是很大，每个字符 长度是 1 字节，我们用大小为 256 的数组，来记录每个字符在模式串中出现的位置。数组 的下标对应字符的 ASCII 码值，数组中存储这个字符在模式串中出现的位置。
哈希表的代码构建过程
private static final int SIZE = 256;//全局变量或成员变量//b为模式串，m为模式串长度，bc为哈希表pivate void generateBC(char[] b,int m,int[] bc){ for(int i = 0;i < SIZE;++i){ bc[i] = -1; //初始化bc } for(int i = 0;i < m;++i){ int ascii = (int)b[i];//计算b[i]的ASCII值 bc[ascii] = i; } } 掌握了坏字符规则之后，我们先把 BM 算法代码的大框架写好，先不考虑好后缀规则，仅 用坏字符规则，并且不考虑 si-xi 计算得到的移动位数可能会出现负数的情况。public int bm(char[] a,int n,char[] b,int m){ int[] bc = new int[SIZE];//记录模式串中每个字符出现的位置 generateBC(b,m,bc);//构建坏字符哈希表 int i = 0;//i表示主串与模式串上下对齐的第一个字符 while(i < n-m){ int j; for(j = m - 1;j >= 0;--j){ //模式串从后往前匹配 if(a[i+j] != b[j]) break; //坏字符对应的模式串中的下标是j } if(j < 0){ return i; //匹配成功，返回主串与模式串第一个匹配的字符的位置 } //这里将等同于模式串往后滑动j-bc[(int)a[i+j]]位 i = i + (j - bc[(int)a[i+j]]); } return -1;}
BM算法代码实现中的关键变量。
大家载坚持一下看完好后缀规则的实现
我们先简单回顾一下，前面讲过好后缀的处理规则中最核心的内容： 在模式串中，查找跟好后缀匹配的另一个子串； 在好后缀的后缀子串中，查找最长的、能跟模式串前缀子串匹配的后缀子串； 在不考虑效率的情况下，这两个操作都可以用很“暴力”的匹配查找方式解决。但是，如果 想要 BM 算法的效率很高，这部分就不能太低效。如何来做呢？ 因为好后缀也是模式串本身的后缀子串，所以，我们可以在模式串和主串正式匹配之前，通 过预处理模式串，预先计算好模式串的每个后缀子串，对应的另一个可匹配子串的位置。这 个预处理过程比较有技巧，很不好懂，应该是这节最难懂的内容了，你要认真多读几遍。 我们先来看，如何表示模式串中不同的后缀子串呢？ 因为后缀子串的最后一个字符的位置是 固定的，下标为 m-1，我们只需要记录长度就可以了。通过长度，我们可以确定一个唯一 的后缀子串现在，我们要 引入最关键的变量 suffix 数组 。suffix 数组的下标 k，表示后缀子串的长 度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。这句话不好理解，我举一个例子。 但是，如果模式串中有多个（大于 1 个）子串跟后缀子串{u}匹配，那 suffix 数组中该存储 哪一个子串的起始位置呢？为了避免模式串往后滑动得过头了，我们肯定要存储模式串中最 靠后的那个子串的起始位置，也就是下标最大的那个子串的起始位置。不过，这样处理就足 够了吗？ 实际上，仅仅是选最靠后的子串片段来存储是不够的。我们再回忆一下好后缀规则。 我们不仅要在模式串中，查找跟好后缀匹配的另一个子串，还要在好后缀的后缀子串中，查 找最长的能跟模式串前缀子串匹配的后缀子串。 如果我们只记录刚刚定义的 suffix，实际上，只能处理规则的前半部分，也就是，在模式串 中，查找跟好后缀匹配的另一个子串。所以，除了 suffix 数组之外，我们还需要另外一个 boolean 类型的 prefix 数组，来记录模式串的后缀子串是否能匹配模式串的前缀子串。
现在，我们来看下， 如何来计算并填充这两个数组的值 ？这个计算过程非常巧妙。 我们拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串。如果 公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）。 如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true。
我们把 suffix 数组和 prefix 数组的计算过程，用代码实现出来，就是下面这个样子：
void generateGS(char[] b,int m,int[] suffix,boolean[] prefix){ for(int i = 0;i < m;++i){ //初始化suffix,prefix数组 suffix[i] = -1; prefix[i] = false; } for(int i = 0;i < m - 1;++i){ //循环处理b[0,i] int j = i; intk = 0;//公共后缀子串的长度 while(j >= 0 && b[j] == b[m-1-k]){ //与b[0,m-1]求公共后缀子串 --j; ++k; suffix[k] = j+1;//j+1表示公共后缀子串在b[0,i]中的起始下标 } if(j == -1) prefix[k] = true; //公共后缀子串也是模式串的前缀子串 }}
有了这两个数组之后，我们现在来看， 在模式串跟主串匹配的过程中，遇到不能匹配的字符 时，如何根据好后缀规则，计算模式串往后滑动的位数？ 假设好后缀的长度是 k。我们先拿好后缀，在 suffix 数组中查找其匹配的子串。如果 suffix[k] 不等于 -1（-1 表示不存在匹配的子串），那我们就将模式串往后移动 j-suffix[k]+1 位（j 表示坏字符对应的模式串中的字符下标）。如果 suffix[k] 等于 -1，表示 模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则来处理。 好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，如果 prefix[k] 等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模 式串后移 r 位。
如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 m 位。
至此，好后缀规则的代码实现我们也讲完了。我们把好后缀规则加到前面的代码框架里，就 可以得到 BM 算法的完整版代码实现。 //a和b分别表示主串和模式串，n和m分别表示主串和模式串的长度public int bm(char[] a,int n,char[] b,int m){ int[] bc = new int[SIZE];//记录模式串中每个字符最后出现的位置 generateBC(b,m,bc);//构建坏字符哈希表 int[] suffix = new int[m]; boolean[] prefix = new boolean[m]; generateGS(b,m,suffix,prefix); int i = 0;//表示主串与模式串匹配的第一个字符 while(i <= n - m){ int j; for(j = m - 1;j >= 0;--j){ //模式串从后往前匹配 if(a[i+j] != b[j]) break; //坏字符对应模式串中的下标是j } if(j < 0){ return i; //匹配成功，返回主串与模式串第一个匹配的字符的位置 } int x = j - bc[(int)a[i+j]]; int y = 0; if(j < m-1){ y = moveByGS(j,m,suffix,prefix); } i = i + Math.max(x,y); } return -1;}//j表示坏字符对应的模式串中的字符下标，m表示模式串长度private int moveByGs(int j,int m,int[] suffix,boolean[] prefix){ int k = m - 1 - j;//好后缀的长度 if(suffix[k] != -1) return j - suffix[k] + 1; for(int r = j+2;r <= m-1;++r){ if(prefix[m-r] == true){ return r; } } return m;} BM 算法的性能分析及优化 我们先来分析 BM 算法的内存消耗。 整个算法用到了额外的 3 个数组，其中 bc 数组的大 小跟字符集大小有关，suffix 数组和 prefix 数组的大小跟模式串长度 m 有关。 如果我们处理字符集很大的字符串匹配问题，bc 数组对内存的消耗就会比较多。因为好后 缀和坏字符规则是独立的，如果我们运行的环境对内存要求苛刻，可以只使用好后缀规则，不使用坏字符规则，这样就可以避免 bc 数组过多的内存消耗。不过，单纯使用好后缀规则 的 BM 算法效率就会下降一些了。 对于执行效率来说，我们可以先从时间复杂度的角度来分析。 基于我目前讨论的这个BM算法，在极端情况下，预处理计算 suffix 数组、prefix 数组 的性能会比较差。 比如模式串是 aaaaaaa 这种包含很多重复的字符的模式串，预处理的时间复杂度就是 O(m^2)。当然，大部分情况下，时间复杂度不会这么差。
引用《数据结构与算法之美》