如果你想了解KMP算法，请静下心来读读这篇文章，绝对不会辜负你的时间BruteForceMatching(BF)字符串匹配是我们编程中的通病。在一个字符串中检测另一个字符串（模式字符串）是一个非常经典的问题。提起这个问题，我们第一个想到的算法可能就是暴力匹配。下面的动画展示了暴力匹配的过程。上图中，当箭头所指的字符全为蓝色时，表示两者匹配，全为黑色时，表示两者不匹配，红色表示在main中找到模式串细绳。该算法的总体思路是，每当模式串与主串不匹配时，将模式串与主串对应的位置向后移动一位，从再次匹配模式串的第一个字符，并重复上述步骤，直到主串中的字符与模式串匹配或匹配主串的最后一位。如果主串和模式串比较短，暴力匹配还是不错的选择，编码也比较容易；但是如果主串和模式串太长，我们想想就知道这个过程非常耗时。那么会不会有相应的优化算法呢？下面介绍一下本文的主角——KMP算法。不说没用的概念，直接说算法的应用过程和使用Python实现算法的代码。最后通过对两者时间复杂度的分析，总结一下为什么KMP算法会比蛮力匹配算法好。KMP算法构建前缀表。我们首先要确定例子的主串和模式串：主串S="abacaababc"和模式串P="ababc"。当模式串与主串相匹配时，我们暂时只看第4步。主串S中的c和模式串P中的b不匹配：如果使用暴力匹配算法，则将模式串P向后移动，从P的第一个字符开始比较。但是现在通过匹配我们可以知道，当第四位不匹配时，可以肯定前三个字符是“aba”。这个已知信息非常有用。KMP算法的核心是利用匹配失败后得到的信息，尽量减少模式串与主串的匹配次数，从而达到快速匹配的目的。比如对于这种不匹配的现象，我们是不是可以直接把pattern串这样移动呢？那么信息从何而来？在KMP算法中，对于一个模式串，可以先计算其内部的匹配信息，这样当匹配失败时，可以最有效地移动模式串，从而减少匹配次数。在此之前，您需要了解前缀和后缀。前缀：abcde的前缀可以是a,ab,abc,abcd后缀：abcde的后缀可以是e,de,cde,bcde这里需要引入一个新的概念——前缀表，可以用profix表示，下标从0开始，profix[i]中存储的信息是前i+1个字符的最长公共后缀和后缀，最长公共后缀和后缀的长度必须小于length的字符串。可以看到“ababc”既不是前缀也不是后缀，但是也列在了表中。如果你了解过KMP算法，你可能听说过下一个数组。前缀表转换为下一个数组时，会覆盖最后一位的值，对流程没有影响。由于本文只依赖前缀表profix来完成KMP算法，所以接下来的数组就不多说了。方法不同只是表述不同，归根结底原理还是一样的。上面的前缀表是通过肉眼对比得到的。程序毕竟不是人，所以需要通过程序可以识别的方法来构造前缀表，按照下图来描述这个过程。通过这个动画，前缀表的构建可以规划为以下五个步骤：首先创建两个指针，指针j指向模式串的第一位（下标为0），指针i指向模式字符串的第二位（下标为1）。由于模式串一开始是单个字符，没有前缀和后缀，所以对应的前缀表的第一位永远为0。当j=0时，比较j和i指向的字符。如果字符不匹配，则i对应的前缀表位置补0，i后移，j不变。当j和i指向的字符匹配时，将i对应的前缀表位置填入(j+1)，j和i都向后移动一位。如果j和i指向的字符不匹配，此时$j\neq0$，j需要回到profix[j-1]的位置，再次与i指向的字符进行比较,重复此步骤直到j和i指向字符匹配或j=0。结合动画看这五个步骤的时候，估计第五步你是看不懂的。看懂了，只能感叹牛逼了。使用下面的例子可以突出第五步的回溯机制。按照上面的步骤，我写出了前缀表的前五位。此时j和i指向的字符不匹配和$j\neq0$，其中j的下标为3，所以需要在前缀表中找到下标为j-1的值，即profix[2]，然后回溯到j对应的位置。这个回溯是因为匹配j和i之间的字符串的前缀可以在模式串的头部找到，即本例中的a。如果此时j和i指向的字符匹配，那么最长公共前缀后缀的长度就是匹配到的前缀(a)的长度加1。可以看出，如果j和i之间的字符串i很长，这个操作可以节省很多时间。此时j和i指向的字符仍然不匹配，则需要继续回溯j，方法同上，回溯位置为profix[0]。此时j和i指向的字符仍然不匹配，但是这里需要做的不是回溯，因为j=0已经满足回溯的结束条件，只要填入i对应的位置即可prefixtable(profix[5])0就够了，肉眼匹配会发现此时确实没有公共前缀和后缀。理解了以上步骤后，就可以看成是伪代码了，根据伪代码很容易写出构造前缀表的函数。defPrefixTable(Pattern):i=1;j=0prefix=[0]*len(Pattern)while(i
