字符串算法—字符串搜索

1. 前文回顾

　　在字符串算法—字典树（Tries）中，我们实现了在一堆字符串中寻找某个字符串的高效算法。但如果要从一段字符中，寻找某个字符串呢？

　　我们可以用字符串算法—字符串排序（下篇）中的后缀排序法（suffix arrays）来寻找关键词，但它消耗的内存有点大（毕竟要建一个超大的数组）。

　　为了解决这个问题，本文将介绍KMP算法(Knuth-Morris-Pratt)和BM算法（Boyer-Moore）。

 

2. KMP算法(Knuth-Morris-Pratt)

　　简单介绍一下问题：

　　现有一段字符：AABACAABABACAA

　　问：ABABAC是否在这段字符里，如果在，在哪里？

　　从解决这个问题的过程中了解KMP算法：

　　

　　左上角那个表格是KMP算法要用到的辅助表格，最下面的那个图是这个表格的图像化（方便理解用），右上角的图为题目中的那段字符。

　　辅助表格如何建立，我们等下再介绍，我们先直接用。辅助表格中的字符是题目要我们找的字符串。

　　为了方便讲解，我们命名题目中的那段字符为字符串S;要寻找的字符为字符串G;即：

　　字符串S: AABACAABABACAA

　　字符串G: ABABAC

　　首先，我们对比S和G的第一个字符，处于辅助表格的第0阶段：

　　

　　由于字符串S只有A,B,C三种字母，所以辅助表格只考虑了A,B,C三种情况。

　　处于第0阶段时，如果遇见的是A，则前往第1阶段；如果遇见的是B或者C，则停留在第0阶段；

　　我们这里遇见的是S的第一个字符A，故前往第1阶段：

　　

　　然后我们来看S的下一个字符A,

　　处于第1阶段时，如果遇见的是A，则停留在第1阶段；如果遇见的是B，则前往第2阶段；如果遇见的是C，则前往第0阶段；

　　现在，我们遇到的是A，故停留在第1阶段：

　　

　　然后我们来看S的下一个字符B,处于第1阶段遇见B，前往第2阶段：（如果有字符已匹配上，则用绿色表示）

　　

　　处于第2阶段时，如果遇见的是A，则前往第3阶段；如果遇见的是B或C，则前往第0阶段

　　我们来看S的下一个字符A，故前往第3阶段：

　　

　　处于第3阶段时，如果遇见的是A，则前往第1阶段；如果遇见的是B，则前往第4阶段；如果遇见的是C，则前往第0阶段；

　　我们来看S的下一个字符C，故前往第0阶段：

　　

　　处于第0阶段时，如果遇见的是A，则前往第1阶段；如果遇见的是B或者C，则停留在第0阶段；

　　我们这里遇见的是S的下一个字符A，故前往第1阶段：

　　

　　处于第1阶段时，如果遇见的是A，则停留在第1阶段；如果遇见的是B，则前往第2阶段；如果遇见的是C，则前往第0阶段；

　　现在，我们遇到的是S的下一个字符A，故停留在第1阶段：

　　

　　处于第1阶段时，如果遇见的是A，则停留在第1阶段；如果遇见的是B，则前往第2阶段；如果遇见的是C，则前往第0阶段；

　　我们遇到的是S的下一个字符B，故前往第2阶段：

　　

　　处于第2阶段时，如果遇见的是A，则前往第3阶段；如果遇见的是B或C，则前往第0阶段

　　我们来看S的下一个字符A，故前往第3阶段：

　　

　　处于第3阶段时，如果遇见的是A，则前往第1阶段；如果遇见的是B，则前往第4阶段；如果遇见的是C，则前往第0阶段；

　　我们来看S的下一个字符B，故前往第4阶段：

　　

　　处于第4阶段时，如果遇见的是A，则前往第5阶段；如果遇见的是B或C，则前往第0阶段

　　我们来看S的下一个字符A，故前往第5阶段：

　　

　　处于第5阶段时，如果遇见的是A，则前往第1阶段；如果遇见的是B，则前往第4阶段；如果遇见的是C，则前往第6阶段；

　　我们来看S的下一个字符C，故前往第6阶段：

　　

　　第6阶段就是最终阶段了，来到这个阶段，说明已经找到字符串G了，至于G在字符串S的什么位置，这个容易求：

　　由于我们是逐个检查字符串S的，（从int i=0开始逐渐递增）所以我们是知道正在检查第几个字符的（i)。

　　int T= i-字符串G的长度+1; T就是字符串G所处位置，在本例子中，T=6，即字符串G在字符串S的第6个字符处。

　　如果我们需要知道某个字符串在某段字符中出现过多少次，分别在哪，则可以在每次找到此字符串时，重新回到第0阶段，继续寻找下去。

　　在本例中，任务完成了，算法结束。

　　顺带一提：所谓的第几阶段就是有几个字符已经匹配上了。例如处于第三阶段时，字符串G和字符串S已经匹配上了3个字符。

　　现在开始讨论如何建立辅助表格：

　　首先最简单的就是每个阶段都遇到了正确的字符，即：

　　我们要查找的字符串G为ABABAC，第0阶段遇到A;第1阶段遇到B;第2阶段遇到A;第3阶段遇到B;第4阶段遇到A;第5阶段遇到C;那么每个阶段都会前往下一个阶段：

　　

　　当我们遇到的是不正确的字符，该怎么办呢？这里新增一个整数型变量int X=0；这个X将起辅助作用。

　　首先第0阶段，只有遇到正确的字符才会前进，否则停留在原地，故：

　　

　　然后到第1阶段，当我们在第X阶段时（X=0），遇到A会前往第1阶段；遇到C会停留在第0阶段。把这个结果填进第1阶段：(图中标红的是第X阶段)

　　

　　然后更新X：现在在第1阶段，第1阶段的字符为B，在第X阶段（X=0）遇到B会停留在第0阶段，故X=0，X值没改变。

　　然后到第2阶段，当我们在第X阶段时（X=0），遇到B会停留在第0阶段；遇到C会停留在第0阶段。把这个结果填进第2阶段：

　　

　　然后更新X：现在在第2阶段，第2阶段的字符为A，在第X阶段（X=0）遇到A会前往第1阶段，故X=1。

　　

　　然后到第3阶段，当我们在第X阶段时（X=1），遇到A会前往第1阶段；遇到C会前往第0阶段。把这个结果填进第3阶段：

　　

　　然后更新X：现在在第3阶段，第3阶段的字符为B，在第X阶段（X=1）遇到B会前往第2阶段，故X=2。

　　

　　然后到第4阶段，当我们在第X阶段时（X=2），遇到B会前往第0阶段；遇到C会前往第0阶段。把这个结果填进第4阶段：

　　

　　然后更新X：现在在第4阶段，第4阶段的字符为A，在第X阶段（X=2）遇到A会前往第3阶段，故X=3。

　　

　　然后到第5阶段，当我们在第X阶段时（X=3），遇到A会前往第1阶段；遇到B会前往第4阶段。把这个结果填进第5阶段：

　　

　　这样辅助表格就做好了。

　　辅助表格的制作过程加上一开始介绍的寻找过程就是完整的KMP算法了。

实现代码

　　建立表格：

　　

　　寻找字符：

　　

 

3. KMP算法效率

　　

　　

　　Brute force(暴风算法）是种蛮力算法，它把要查找的字符串与原字符串的第一个字符开始一一对比，如果发现不匹配的字符，则从下一个字符开始一一个对比。如此类推，直到找到了该字符串或原字符串所有字符都对比完（找不到该字符串的情况）为止。

　　由于此算法效率低下，这里没有细讲。

　　图中N为原字符串所含字符数量；M为要找的字符串所含字符数量，R为字符串中可能出现的字符种类数量，根据下图选择：

　　

 

4. BM算法（Boyer-Moore）

　　百度了一下：在用于查找子字符串的算法当中，BM（Boyer-Moore）算法是目前被认为最高效的字符串搜索算法，它由Bob Boyer和J Strother Moore设计于1977年。 一般情况下，比KMP算法快3-5倍。

　　这个算法牛的地方在于要查找的字符串越长，搜索效率越高。

　　从例子入手：

　　

　　

　　如上图，我们把所有的字符的值定为-1，要查找的字符串needle含有4个不同的字符，我们根据它们所处位置给它们赋值：right[N]=0; right[E]=5; right[D]=3; right[L]=4；其中E出现了3次，我们取其中的最大值。

　　新增整数变量 int i=0; int j=0; 原字符串长度N=24； 查找的字符串长度M=6;

　　首先。j=M-1；即j=5；从第j个字符开始比较：

　　

　　比较结果：不相等。

　　然后要决定我们可以跳几个字符：原字符串的第5个字符为N，right[N]=0; j-right[N]=5-0=5; 故我们可以跳5个字符：i +=5; i=5;

　　

　　j+i=5+5=10；比较原字符的第10个字符：

　　

　　比较结果：不相等。

　　然后要决定我们可以跳几个字符：原字符串的第10个字符为S，right[S]=-1; j-right[S]=5-(-1)=6; 故我们可以跳6个字符(因为s不在要查找的字符串里，所以可以把这整段跳过去)：i +=6; i=11;

　　

　　j+i=5+11=16；比较原字符的第16个字符：

　　

　　比较结果：相等。比较前一个字符, j--; j=5-1=4：

　　

　　计较结果：相等。

　　然后要决定我们可以跳几个字符：原字符串的第15个字符为N，right[N]=0; j-right[N]=4-0=4; 故我们可以跳4个字符：i +=4; i=15, j=M; j=5;

　　

　　j+i=5+15=20；比较原字符的第20个字符：

　　

　　比较结果：相等。比较前一个字符, j--; j=5-1=4：

　　

　　比较结果：相等。比较前一个字符, j--; j=4-1=3：（由于接下来的结果都是相等，故省略中间过程，直接跳到j=0）

　　

　　比较结果：相等。由于j=0；再减下去就是负数了，算法也在这里结束。要查找的字符串在原字符的第i个字符处（i=15）。

　　另外，值得一提的是，请看以下情况：

　　

　　此时，j=3, 比较结果不相同。

　　然后要决定我们可以跳几个字符：原字符串的第18个字符为E，right[E]=5; j-right[E]=3-5=-2; 跳的步数为负数，我们总不能往回跳吧！故当跳的步数为负时，我们只往前跳一个字符：　　

　　

　　此时如果再跳，就要跳出字符串之外了，故当i>N-M时，我们停止算法，判断结果为没找到该字符。

　　当我们的要找的字符串越长时，我们可能能跳的字符数也越多，算法越快。（为什么是可能？因为当原字符串的字符都出现在要查找的字符串时，是没办法跳M个字符的。）

 

实现代码：

　　

　　

 

5. BM算法效率

　　

　　图中N为原字符串所含字符数量；M为要找的字符串所含字符数量，R为字符串中可能出现的字符种类数量。

　　但是，如果遇到最坏情况：

　　

　　在这种情况下，BM算法跳不了，只能一步一步往前比较。此时就等于是Brute force(暴风算法)了。

• 还没有人评论，欢迎说说您的想法！