33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.pdf

《33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.pdf》由会员分享，可在线阅读，更多相关《33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.pdf（30页珍藏版）》请在三一文库上搜索。

1、33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ 文本编辑器中的查找替换功能，我想你应该不陌生吧？比如，我们在Word中把一个单词统一替换成另一个，用的就是这个功能。你有没有想过，它是怎么实现的 呢？ 当然，你用上一节讲的BF算法和RK算法，也可以实现这个功能，但是在某些极端情况下，BF算法性能会退化的比较严重，而RK算法需要用到哈希算法，而设计 一个可

2、以应对各种类型字符的哈希算法并不简单。 对于工业级的软件开发来说，我们希望算法尽可能的高效，并且在极端情况下，性能也不要退化的太严重。那么，对于查找功能是重要功能的软件来说，比如一 些文本编辑器，它们的查找功能都是用哪种算法来实现的呢？有没有比BF算法和RK算法更加高效的字符串匹配算法呢？ 今天，我们就来学习BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的3到4倍。BM算法的原理很复 杂，比较难懂，学起来会比较烧脑，我会尽量给你讲清楚，同时也希望你做好打硬仗的准备。好，现在我们正式开始！ BM算法的核心思想 我们把模式串和主串的匹配

3、过程，看作模式串在主串中不停地往后滑动。当遇到不匹配的字符时，BF算法和RK算法的做法是，模式串往后滑动一位，然后从模式 串的第一个字符开始重新匹配。我举个例子解释一下，你可以看我画的这幅图。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 在这个例子里，主串中的c，在模式串中是不存在的，所以，模式串向后滑动的时候，只要c与模式串有重合，肯定无法匹配。所以，我们可以一次性把模式串往 后多滑动几位，把模式串移动到c

4、的后面。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 由现象找规律，你可以思考一下，当遇到不匹配的字符时，有什么固定的规律，可以将模式串往后多滑动几位呢？这样一次性往后滑动好几位，那匹配的效率岂 不是就提高了？ 我们今天要讲的BM算法，本质上其实就是在寻找这种规律。借助这种规律，在模式串与主串匹配的过程中，当模式串和主串某个字符不匹配的时候，能够跳过一 些肯定不会匹配的情况，将模式串往后多滑动几位。 BM算法

5、原理分析 BM算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）。我们下面依次来看，这两个规则分别都是怎么工作的。 1.坏字符规则 前面两节讲的算法，在匹配的过程中，我们都是按模式串的下标从小到大的顺序，依次与主串中的字符进行匹配的。这种匹配顺序比较符合我们的思维习惯， 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 而BM算法的匹配顺序比较

6、特别，它是按照模式串下标从大到小的顺序，倒着匹配的。我画了一张图，你可以看下。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 我们从模式串的末尾往前倒着匹配，当我们发现某个字符没法匹配的时候。我们把这个没有匹配的字符叫作坏字符（主串中的字符）。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑

7、器中的查找功能？.html2019/1/15 15:36:12 我们拿坏字符c在模式串中查找，发现模式串中并不存在这个字符，也就是说，字符c与模式串中的任何字符都不可能匹配。这个时候，我们可以将模式串直接往 后滑动三位，将模式串滑动到c后面的位置，再从模式串的末尾字符开始比较。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 这个时候，我们发现，模式串中最后一个字符d，还是无法跟主串中的a匹配，这个时候，还能将模

8、式串往后滑动三位吗？答案是不行的。因为这个时候，坏字 符a在模式串中是存在的，模式串中下标是0的位置也是字符a。这种情况下，我们可以将模式串往后滑动两位，让两个a上下对齐，然后再从模式串的末尾字符开 始，重新匹配。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 第一次不匹配的时候，我们滑动了三位，第二次不匹配的时候，我们将模式串后移两位，那具体滑动多少位，到底有没有规律呢？ 当发生不匹配的时候，我们把坏字符对应

9、的模式串中的字符下标记作si。如果坏字符在模式串中存在，我们把这个坏字符在模式串中的下标记作xi。如果不存在， 我们把xi记作-1。那模式串往后移动的位数就等于si-xi。（注意，我这里说的下标，都是字符在模式串的下标）。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 这里我要特别说明一点，如果坏字符在模式串里多处出现，那我们在计算xi的时候，选择最靠后的那个，因为这样不会让模式串滑动过多，导致本来可能匹配的情

10、 况被滑动略过。 利用坏字符规则，BM算法在最好情况下的时间复杂度非常低，是O(n/m)。比如，主串是aaabaaabaaabaaab，模式串是aaaa。每次比对，模式串都可以直接后移四 位，所以，匹配具有类似特点的模式串和主串的时候，BM算法非常高效。 不过，单纯使用坏字符规则还是不够的。因为根据si-xi计算出来的移动位数，有可能是负数，比如主串是aaaaaaaaaaaaaaaa，模式串是baaa。不但不会向后滑动模式 串，还有可能倒退。所以，BM算法还需要用到“好后缀规则”。 2.好后缀规则 好后缀规则实际上跟坏字符规则的思路很类似。你看我下面这幅图。当模式串滑动到图中的位置的时候，模式

11、串和主串有2个字符是匹配的，倒数第3个字符发生 了不匹配的情况。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 这个时候该如何滑动模式串呢？当然，我们还可以利用坏字符规则来计算模式串的滑动位数，不过，我们也可以使用好后缀处理规则。两种规则到底如何选择， 我稍后会讲。抛开这个问题，现在我们来看，好后缀规则是怎么工作的？ 我们把已经匹配的bc叫作好后缀，记作u。我们拿它在模式串中查找，如果找到了另一个跟u相匹配的子

12、串u*，那我们就将模式串滑动到子串u*与主串 中u对齐的位置。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 如果在模式串中找不到另一个等于u的子串，我们就直接将模式串，滑动到主串中u的后面，因为之前的任何一次往后滑动，都没有匹配主串中u的情况。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编

13、辑器中的查找功能？.html2019/1/15 15:36:12 不过，当模式串中不存在等于u的子串时，我们直接将模式串滑动到主串u的后面。这样做是否有点太过头呢？我们来看下面这个例子。这里面bc是好后缀，尽 管在模式串中没有另外一个相匹配的子串u*，但是如果我们将模式串移动到好后缀的后面，如图所示，那就会错过模式串和主串可以匹配的情况。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 33|字符串匹配基础（中）

14、：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 如果好后缀在模式串中不存在可匹配的子串，那在我们一步一步往后滑动模式串的过程中，只要主串中的u与模式串有重合，那肯定就无法完全匹配。但是当模 式串滑动到前缀与主串中u的后缀有部分重合的时候，并且重合的部分相等的时候，就有可能会存在完全匹配的情况。 所以，针对这种情况，我们不仅要看好后缀在模式串中，是否有另一个匹配的子串，我们还要考察好后缀的后缀子串，是否存在跟模式串的前缀子串匹配的。 所谓某

15、个字符串s的后缀子串，就是最后一个字符跟s对齐的子串，比如abc的后缀子串就包括c, bc。所谓前缀子串，就是起始字符跟s对齐的子串，比如abc的前缀子 串有a，ab。我们从好后缀的后缀子串中，找一个最长的并且能跟模式串的前缀子串匹配的，假设是v，然后将模式串滑动到如图所示的位置。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 坏字符和好后缀的基本原理都讲完了，我现在回答一下前面那个问题。当模式串和主串中的某个

16、字符不匹配的时候，如何选择用好后缀规则还是坏字符规则，来 计算模式串往后滑动的位数？ 我们可以分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数。这种处理方法还可以避免我们前面提到的，根据坏字 符规则，计算得到的往后滑动的位数，有可能是负数的情况。 BM算法代码实现 学习完了基本原理，我们再来看，如何实现BM算法？ “坏字符规则”本身不难理解。当遇到坏字符时，要计算往后移动的位数si-xi，其中xi的计算是重点，我们如何求得xi呢？或者说，如何查找坏字符在模式串中出现 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/ge

17、ektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 的位置呢？ 如果我们拿坏字符，在模式串中顺序遍历查找，这样就会比较低效，势必影响这个算法的性能。有没有更加高效的方式呢？我们之前学的散列表，这里可以派上 用场了。我们可以将模式串中的每个字符及其下标都存到散列表中。这样就可以快速找到坏字符在模式串的位置下标了。 关于这个散列表，我们只实现一种最简单的情况，假设字符串的字符集不是很大，每个字符长度是1字节，我们用大小为256的数组，来记录每个字符在模式串中 出现的位置。数组的下标对应字符的ASCII码值，数组

18、中存储这个字符在模式串中出现的位置。 如果将上面的过程翻译成代码，就是下面这个样子。其中，变量b是模式串，m是模式串的长度，bc表示刚刚讲的散列表。 private static final int SIZE = 256; / 全局变量或成员变量 private void generateBC(char b, int m, int bc) for (int i = 0; i = 0; -j) / 模式串从后往前匹配 if (ai+j != bj) break; / 坏字符对应模式串中的下标是j if (j = 0 +k; suffixk = j+1; /j+1表示公共后缀子串在b0, i中的起

19、始下标 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 i if (j = -1) prefixk = true; /如果公共后缀子串也是模式串的前缀子串 有了这两个数组之后，我们现在来看，在模式串跟主串匹配的过程中，遇到不能匹配的字符时，如何根据好后缀规则，计算模式串往后滑动的位数？ 假设好后缀的长度是k。我们先拿好后缀，在suffix数组中查找其匹配的子串。如果suffixk不等于-1（-1表示不存在匹配的子

20、串），那我们就将模式串往后移动j- suffixk+1位（j表示坏字符对应的模式串中的字符下标）。如果suffixk等于-1，表示模式串中不存在另一个跟好后缀匹配的子串片段。我们可以用下面这条规则 来处理。 好后缀的后缀子串br, m-1（其中，r取值从j+2到m-1）的长度k=m-r，如果prefixk等于true，表示长度为k的后缀子串，有可匹配的前缀子串，这样我们可以把模 式串后移r位。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019

21、/1/15 15:36:12 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移m位。 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 至此，好后缀规则的代码实现我们也讲完了。我们把好后缀规则加到前面的代码框架里，就可以得到BM算法的完整版代码实现。 / a,b表示主串和模式串；n，m表示主串和模式串的长度。 public int bm(char a, int n, char b, i

22、nt m) int bc = new intSIZE; / 记录模式串中每个字符最后出现的位置 generateBC(b, m, bc); / 构建坏字符哈希表 int suffix = new intm; boolean prefix = new booleanm; generateGS(b, m, suffix, prefix); int i = 0; / j表示主串与模式串匹配的第一个字符 while (i = 0; -j) / 模式串从后往前匹配 if (ai+j != bj) break; / 坏字符对应模式串中的下标是j if (j 0) return i; / 匹配成功，返回主串

23、与模式串第一个匹配的字符的位置 int x = j - bc(int)ai+j; int y = 0; if (j m-1) / 如果有好后缀的话 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 y = moveByGS(j, m, suffix, prefix); i = i + Math.max(x, y); return -1; / j表示坏字符对应的模式串中的字符下标; m表示模式串长度 private

24、int moveByGS(int j, int m, int suffix, boolean prefix) int k = m - 1 - j; / 好后缀长度 if (suffixk != -1) return j - suffixk +1; for (int r = j+2; r = m-1; +r) if (prefixm-r = true) return r; return m; BM算法的性能分析及优化 我们先来分析BM算法的内存消耗。整个算法用到了额外的3个数组，其中bc数组的大小跟字符集大小有关，suffix数组和prefix数组的大小跟模式串长度m有关。 如果我们处理字符集很

25、大的字符串匹配问题，bc数组对内存的消耗就会比较多。因为好后缀和坏字符规则是独立的，如果我们运行的环境对内存要求苛刻，可以 只使用好后缀规则，不使用坏字符规则，这样就可以避免bc数组过多的内存消耗。不过，单纯使用好后缀规则的BM算法效率就会下降一些了。 对于执行效率来说，我们可以先从时间复杂度的角度来分析。 实际上，我前面讲的BM算法是个初级版本。为了让你能更容易理解，有些复杂的优化我没有讲。基于我目前讲的这个版本，在极端情况下，预处理计算suffix数 组、prefix数组的性能会比较差。 比如模式串是aaaaaaa这种包含很多重复的字符的模式串，预处理的时间复杂度就是O(m2)。当然，大部

26、分情况下，时间复杂度不会这么差。关于如何优化这种极 端情况下的时间复杂度退化，如果感兴趣，你可以自己研究一下。 实际上，BM算法的时间复杂度分析起来是非常复杂，这篇论文“A new proof of the linearity of the Boyer-Moore string searching algorithm”证明了在最坏情况 下，BM算法的比较次数上限是5n。这篇论文“Tight bounds on the complexity of the Boyer-Moore string matching algorithm”证明了在最坏情况下，BM算法的比较次数 上限是3n。你可以自己阅读

27、看看。 解答开篇&内容小结 今天，我们讲了一种比较复杂的字符串匹配算法，BM算法。尽管复杂、难懂，但匹配的效率却很高，在实际的软件开发中，特别是一些文本编辑器中，应用比较 多。如果一遍看不懂的话，你就多看几遍。 BM算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配 的效率。BM算法构建的规则有两类，坏字符规则和好后缀规则。好后缀规则可以独立于坏字符规则使用。因为坏字符规则的实现比较耗内存，为了节省内存，我 们可以只用好后缀规则来实现BM算法。 课后思考 33|字符串匹配基础（中）：如何实现文本编辑器中的查

28、找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 你熟悉的编程语言中的查找函数，或者工具、软件中的查找功能，都是用了哪种字符串匹配算法呢？ 欢迎留言和我分享，也欢迎点击“请朋友读”，把今天的内容分享给你的好友，和他一起讨论、学习。 精选留言： Smallfly 2018-12-08 09:48:37 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑

29、器中的查找功能？.html2019/1/15 15:36:12 BM 算法分析着实比较复杂，不过按照老师的思路，一步一步走，看懂应该没问题的。但其实有些代码实现细节看不懂关系也不大。我们学算法主要目的是 学习算法的思想，能在需要的时候加以应用就好。 但对于平时工作，几乎不可能遇到，需要自己手写一个字符串匹配算法的场景。那我们还要学，图的是什么？ 我认为文章中值得学习借鉴的思想有： 1、要有优化意识，前面的 BF，RK 算法已经能够满足我们需求了，为什么发明 BM 算法？是为了减少时间复杂度，但是带来的弊端是，优化代码变得复杂 ，维护成本变高。 2、需要查找，需要减少时间复杂度，应该想到什么？散

30、列表。 3、如果某个表达式计算开销比较大，又需要频繁的使用怎么办？预处理，并缓存。 （一点拙见，可能文中还有其它优秀的思想，没能 Get 到） 24赞 作者回复2018-12-10 02:00:29 meng 2018-12-09 02:48:32 我对这次课的内容一知半解，于是在网上搜到一个文档，里面的图挺好的，跟大家分享一下：http:/www.cs.jhu.edu/langmea/resources/lecture_notes/boyer_mo ore.pdf 18赞 Liam 2018-12-07 04:51:58 好后缀原则下，最后一种情况为什么移到坏字符后面呢，不能移到好后缀的后面

31、吗？即m+1,而不是j + 1 7赞 作者回复2018-12-07 06:39:10 你说的对 我改下 meng 2018-12-23 04:16:41 这篇文章啃了很长时间了，有个问题请教：是否可以不要prefix数组，直接通过suffixk=0来判断前缀子串的匹配与否？ 6赞 Jerry银银 2018-12-07 05:02:53 曾经一度觉得字符串匹配的几大算法，都是高山仰止的，难以理解。 但是前阵子受两句话启发，从此以后对字符串匹配问题，至少在战略层面藐视了它： 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美

32、/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 1. 善用之前信息(从信息论的角度：消除信息的不确定性，就是引入信息) 2. 增加效率，在资源有限的情况下，只有想办法少做事情 6赞 纯洁的憎恶 2018-12-10 10:06:39 大体思路应该是看懂了，不过具体实现和代码细节还需要时间消化。BM算法的核心思想是通过将模式串沿着主串大踏步的向后滑动，从而大大减少比较次 数，降低时间复杂度。而算法的关键在于如何兼顾步子迈得足够大与无遗漏，同时要尽量提高执行效率。这就需要模式串在向后滑动时，遵守坏字符规则与 好后缀规则，同时采用一些技巧。

33、 坏字符规则：从后往前逐位比较模式串与主串的字符，当找到不匹配的坏字符时，记录模式串的下标值si，并找到坏字符在模式串中，位于下标si前的最近位 置xi（若无则记为-1），si-xi即为向后滑动距离。（PS：我觉得加上xi必须在si前面，也就是比si小的条件，就不用担心计算出的距离为负了）。但是坏字符 规则向后滑动的步幅还不够大，于是需要好后缀规则。 好后缀规则：从后往前逐位比较模式串与主串的字符，当出现坏字符时停止。若存在已匹配成功的子串u，那么在模式串的u前面找到最近的u ，记作u。再将模式串后移，使得模式串的u与主串的u重叠。若不存在u，则直接把模式串移到主串的u后面。为了没有遗漏，需要

34、找 到最长的、能够跟模式串的前缀子串匹配的，好后缀的后缀子串（同时也是模式串的后缀子串）。然后把模式串向右移到其左边界，与这个好后缀的后缀子 串在主串中的左边界对齐。 何时使用坏字符规则和好后缀规则呢？首先在每次匹配过程中，一旦发现坏字符，先执行坏字符规则，如果发现存在好后缀，还要执行好后缀规则，并从两 者中选择后移距离最大的方案执行。 技巧： 1.通过散列表实现，坏字符在模式串中下标位置的快速查询。 2.每次执行好后缀原则时，都会计算多次能够与模式串前缀子串相匹配的好后缀的最长后缀子串。为了提高效率，可以预先计算模式串的所有后缀子串，在 模式串中与之匹配的另一个子串的位置。同时预计算模式串中

35、（同长度的）后缀子串与前缀子串是否匹配并记录。在具体操作中直接使用，大大提高效率。 3.如何快速记录模式串后缀子串匹配的另一个子串位置，以及模式串（相同长度）前缀与后缀子串石否匹配呢？先用一个suffix数组，下标值k为后缀子串的 长度，从模式串下标为i（0m-2）的字符为最后一个字符，查找这个子串是否与后缀子串匹配，若匹配则将子串起始位置的下标值j赋给suffixk。若j为0， 说明这个匹配子串的起始位置为模式串的起始位置，则用一个数组prefix，将prefixk设为true，否则设为false。k从0到m（模式串的长度）于是就得到了模式 串所有前缀与后缀子串的匹配情况。 4赞 五岳寻仙

36、2018-12-06 23:45:30 老师好！今天讲的BM算法确实有点复杂，不过听的时候有熟悉的感觉，似乎跟之前接触过的Boyer Moore算法很像，查了一下才发现原来是同一种算法 在工作中遇到过这样的情况，需要在一个长度为n (比如十亿级)的巨大的主串中查找长度为m(比如几百)的模式串。主串是固定的，从直观上讲，要加快搜索 33|字符串匹配基础（中）：如何实现文本编辑器中的查找功能？ file:/F/temp/geektime/数据结构与算法之美/33字符串匹配基础（中）：如何实现文本编辑器中的查找功能？.html2019/1/15 15:36:12 速度，就需要对主串建索引。BWT-F

37、M算法是解决这类问题最经典的算法，刚接触时也是不好理解，但感觉非常神奇，可以将搜索的时间复杂度降到O(m)， 是我认为最伟大的算法之一。 4赞 suke 2018-12-19 06:35:29 老师以后的代码中的变量能不能起的有意义一些，这样更加方便大家理解代码啊，不要总拿a b c bc这种完全没有意义的名字来命名变量 3赞 cygnus 2018-12-08 08:37:52 generateGS函数里suffix和prefix的赋值应该放到while循环内，即每次k变动时都要赋值。 另外请问下：好后缀的后缀子串 br, m-1，这里的r的初值j+2是怎么得来的啊？ 3赞 作者回复2018-12-10 02:06:17 j表示坏字符的下标 好狗追其实下标j+1 seniusen 2018-12-07 11:34:30 好后缀原则中，最后一种情况，应该是移动 m 位吧，移动整个模式串的长度。 3赞 作者回复2018-12-10 02:10:22 是的