字符串算法—字符串搜索,字符串算法—字符串排序（下篇）
1. 前文回顾
在字符串算法—字典树（Tries）中，我们实现了在一堆字符串中寻找某个字符串的高效算法。但如果要从一段字符中，寻找某个字符串呢？
我们可以用字符串算法—字符串排序（下篇）中的后缀排序法（suffix arrays）来寻找关键词，但它消耗的内存有点大（毕竟要建一个超大的数组）。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。为了解决这个问题，本文将介绍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(暴风算法)了。
