然后引用下之前3.1节的KMP代码：

int KmpSearch(char* s, char* p)

{

int i = 0;

int j = 0;

int sLen = strlen(s);

int pLen = strlen(p);

while (i < sLen && j < pLen)

{

//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++    

if (j == -1 || s[i] == p[j])

{

i++;

j++;

}

else

{

//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    

//next[j]即为j所对应的next值      

j = next[j];

}

}

if (j == pLen)

return i – j;

else

return -1;

}

接下来，咱们继续拿之前的例子说明，整个匹配过程如下：

1. S[3]与P[3]匹配失败。

 2. S[3]保持不变，P的下一个匹配位置是P[next[3]]，而next[3]=0，所以P[next[3]]=P[0]与S[3]匹配。

3.  由 于上一步骤中P[0]与S[3]还是不匹配。此时i=3，j=next [0]=-1，由于满足条件j==-1，所以执行“++i, ++j”，即主串指针下移一个位置，P[0]与S[4]开始匹配。最后j==pLen，跳出循环，输出结果i – j = 4（即模式串第一次在文本串中出现的位置），匹配成功，算法结束。

   

3.4 KMP的时间复杂度分析

    相信大部分读者读完上文之后，已经发觉其实理解KMP非常容易，无非是循序渐进把握好下面几点：
  1. 如果模式串中存在相同前缀和后缀，即pj-k pj-k+1, …, pj-1 = p0 p1, …, pk-1，那么在pj跟si失配后，让模式串的前缀p0 p1…pk-1对应着文本串si-k si-k+1…si-1，而后让pk跟si继续匹配。
  2. 之前本应是pj跟si匹配，结果失配了，失配后，令pk跟si匹配，相当于j 变成了k，模式串向右移动j – k位。
  3. 因 为k 的值是可变的，所以我们用next[j]表示j处字符失配后，下一次匹配模式串应该跳到的位置。换言之，失配前是j，pj跟si失配时，用p[ next[j] ]继续跟si匹配，相当于j变成了next[j]，所以，j = next[j]，等价于把模式串向右移动j – next [j] 位。
  4. 而next[j]应该等于多少呢？next[j]的值由j 之前的模式串子串中有多大长度的相同前缀后缀所决定，如果j 之前的模式串子串中（不含j）有最大长度为k的相同前缀后缀，那么next [j] = k。
    如之前的图所示：
    接下来，咱们来分析下KMP的时间复杂度。分析之前，先来回顾下KMP匹配算法的流程：

“KMP的算法流程：

  • 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
    • 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
    • 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j – next [j] 位。”

我们发现如果某个字符匹配成功，模式串首字符的位置保持不动，仅仅是i++、j++；如果匹配失配，i 不变（即 i 不回溯），模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是，当模式串首字符位于i – j的位置时才匹配成功，算法结束。
所以，如果文本串的长度为n，模式串的长度为m，那么匹配过程的时间复杂度为O(n)，算上计算next的O(m)时间，KMP的整体时间复杂度为O(m + n)。

 

4. 扩展1：BM算法

KMP的匹配是从模式串的开头开始匹配的，而1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了一种新的字符串匹配算法：Boyer-Moore算法，简称BM算法。该算法从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的 时间复杂度。在实践中，比KMP算法的实际效能高。

BM算法定义了两个规则：

  • 坏字符规则：当文本串中的某 个字符跟模式串的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串需要向右移动，移动的位数 = 坏字符在模式串中的位置 – 坏字符在模式串中最右出现的位置。此外，如果”坏字符”不包含在模式串之中，则最右出现位置为-1。
  • 好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 – 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。

下面举例说明BM算法。例如，给定文本串“HERE IS A SIMPLE EXAMPLE”，和模式串“EXAMPLE”，现要查找模式串是否在文本串中，如果存在，返回模式串在文本串中的位置。

1. 首 先，”文本串”与”模式串”头部对齐，从尾部开始比较。”S”与”E”不匹配。这时，”S”就被称为”坏字符”（bad character），即不匹配的字符，它对应着模式串的第6位。且”S”不包含在模式串”EXAMPLE”之中（相当于最右出现位置是-1），这意味着 可以把模式串后移6-(-1)=7位，从而直接移到”S”的后一位。

2. 依 然从尾部开始比较，发现”P”与”E”不匹配，所以”P”是”坏字符”。但是，”P”包含在模式串”EXAMPLE”之中。因为“P”这个“坏字符”对应 着模式串的第6位（从0开始编号），且在模式串中的最右出现位置为4，所以，将模式串后移6-4=2位，两个”P”对齐。

3. 依次比较，得到 “MPLE”匹配，称为”好后缀”（good suffix），即所有尾部匹配的字符串。注意，”MPLE”、”PLE”、”LE”、”E”都是好后缀。

4. 发现“I”与“A”不匹配：“I”是坏字符。如果是根据坏字符规则，此时模式串应该后移2-(-1)=3位。问题是，有没有更优的移法？

5. 更优的移法是利用好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 – 好后缀在模式串中上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。
所有的“好后缀”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPLE”的头部出现，所以后移6-0=6位。
可以看出，“坏字符规则”只能移3位，“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数，只与模式串有关，与原文本串无关。

6. 继续从尾部开始比较，“P”与“E”不匹配，因此“P”是“坏字符”，根据“坏字符规则”，后移 6 – 4 = 2位。因为是最后一位就失配，尚未获得好后缀。

由上可知，BM算法不仅效率高，而且构思巧妙，容易理解。

5. 扩展2：Sunday算法

上文中，我们已经介绍了KMP算法和BM算法，这两个算法在最坏情况下均具有线性的查找时间。但实际上，KMP算法并不比最简单的c库函数 strstr()快多少，而BM算法虽然通常比KMP算法快，但BM算法也还不是现有字符串查找算法中最快的算法，本文最后再介绍一种比BM算法更快的查 找算法即Sunday算法。

Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：

  • 只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。
    • 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1；
    • 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1。

下面举个例子说明下Sunday算法。假定现在要在文本串”substring searching algorithm”中查找模式串”search”。

1. 刚开始时，把模式串与文本串左边对齐：
substring searching algorithm
search
^
2. 结果发现在第2个字符处发现不匹配，不匹配时关注文本串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 匹配串长度 + 1 = 6 + 1 = 7，从 i 之后的那个字符（即字符n）开始下一步的匹配，如下图：

substring searching algorithm
　　　 search
^
3. 结果第一个字符就不匹配，再看文本串中参加匹配的最末位字符的下一位字符，是’r’，它出现在模式串中的倒数第3位，于是把模式串向右移动3位（r 到模式串末尾的距离 + 1 = 2 + 1 =3），使两个’r’对齐，如下：
substring searching algorithm
　　　　  search
^

4. 匹配成功。

回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于Sunday算法每一步的移动量都比较大，效率很高。完。

6. 参考文献

  1. 《算法导论》的第十二章：字符串匹配；
  2. 本文中模式串“ABCDABD”的部分图来自于此文：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html；
  3. 本文3.3.7节中有限状态自动机的图由微博网友@龚陆安 绘制：http://d.pr/i/NEiz；
  4. 北京7月暑假班邹博半小时KMP视频：http://v.youku.com/v_show/id_XNzQzMjQ1OTYw.html；
  5. 北京7月暑假班邹博第二次课的PPT：http://yun.baidu.com/s/1mgFmw7u；
  6. 理解KMP 的9张PPT：http://weibo.com/1580904460/BeCCYrKz3#_rnd1405957424876；
  7. 详解KMP算法（多图）：http://www.cnblogs.com/yjiyjige/p/3263858.html；
  8. 本文第4部分的BM算法参考自此文：http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html；
  9. http://youlvconglin.blog.163.com/blog/static/5232042010530101020857；
  10. 《数据结构 第二版》，严蔚敏 & 吴伟民编著；
  11. http://blog.csdn.net/v_JULY_v/article/details/6545192；
  12. http://blog.csdn.net/v_JULY_v/article/details/6111565；
  13. Sunday算法的原理与实现：http://blog.chinaunix.net/uid-22237530-id-1781825.html；
  14. 模式匹配之Sunday算法：http://blog.csdn.net/sunnianzhong/article/details/8820123；
  15. 一篇KMP的英文介绍：http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm；
  16. 我2014年9月3日在西安电子科技大学的面试&算法讲座视频（第36分钟~第94分钟讲KMP）：http://v.youku.com/v_show/id_XNzc2MDYzNDg4.html。

7. 后记

对之前混乱的文章给广大读者带来的困扰表示致歉，对重新写就后的本文即将给读者带来的清晰表示欣慰。希望大部分的初学者，甚至少部分的非计算机专业读者也能看懂此文。有任何问题，欢迎随时批评指正，thanks。

July、二零一四年八月二十二日晚九点。