【CPP】简单的字符串匹配（1）——BF算法与KMP算法

字符串匹配是计算机科学中最古老、研究最广泛的问题之一。我们有很多时候需要在一个较长的字符串寻找出现的子串的位置。在字符串不长时，我们对效率可能还没有太多需求，但是当字符串很长时，便需要一个效率优秀的算法来进行更好的字符串匹配了。这次我们便引入C++的<string>头文件，利用里面的string类来进行两种算法的简单介绍。

首先我们先写一下我们这个字符串匹配类，先是声明。

然后是类的初始化部分。在这里我们先将字符串声明为空串，再调用自带的assign函数为其赋值，然后获取它的长度。

然后先是我们最容易想到的算法，BF算法——暴风(Brute Force)算法。这是最简单的蛮力匹配算法。简单说就是一个一个位地去匹配字符串。这次我试试主要把解释写在代码的注释里，感觉这样写方便代码与解释的相互对照（懒）。

然而虽然BF匹配很方便易想，但是它的效率很低。时间复杂度是O(n*m)。而它的效率低主要是在当主串中出现很多部分匹配串时算法会不断进行重复无用的匹配。这里我们想象一下，如果有主串00000000001，模式串00001，这时候如果我们用BF算法来匹配会是怎样的结果？你会发现模式指针和主串指针回溯匹配了很多很多次，但是这些匹配其实是无用的。当我们第一次匹配时，模式串匹配到1时，我们发现匹配失败了，然后我们看，其实我们只要拿1之前的一个字符和失配的字符匹配一下如果匹配成功就继续匹配，匹配失败就整个模式串可以跳跃前进到失配处了（因为开始的4的字符都是0，一个匹配失败剩下的一定也是失败的）。我们其实并没有必要不断回溯主串的指针来匹配，我们可以按照一定的规则跳跃模式串来进行匹配，这就是KMP算法的思想，利用已经匹配成功的子串作为之后匹配的经验，利用模式串自身的特典来加速匹配。但是刚才我们为什么要先从1跳回0再跳回开头呢？这便是我们要找到的模式串的自身特典，一个包含下标的数组，我们把它称为next数组。利用这个数组我们可以跳跃移动模式串来匹配。

于是下面就是KMP算法——一种由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人设计的线性时间字符串匹配算法。其中的D.E.Knuth就是这文章的封面，写下《计算机程序设计的艺术》巨著的大师。

首先在理解KMP的思想下，我们先假设已经有了一个next数组来写一个KMP算法。

主体的思路并不复杂，主要就是要理解k=next[k]这句，如果不理解可以试试看画画图理解。

然后便是整个KMP的核心，如何算出NEXT数组也就是GetNext函数。

代码实际上并不长，其中最重要的也是k=next[k];这句，还是一样，多画图，与Find函数相类比会比较容易理解。

这个算法的时间复杂度还是O(n*m)，但是实际使用中执行时间近似于O(n+m)，是一个很快很实用的算法。不过next函数其实还可以优化一下，当模式串中大量元素连续相等时，模式串在滑动时可以一口气滑过这些元素（上面简介中的方法），只要简单地改一下while循环内部就能解决这个问题。

这样便完成了KMP的编写，简单包装一下，让其匹配中顺便输出next数组，写一个简单的函数便完成。

写的有点简单了，也没配什么好的图，感觉应该不好懂吧hhh

依然附上代码。

链接：http://pan.baidu.com/s/1jH5DuNO 密码：zf46