一.理论准备
KMP算法为什么比传统的字符串匹配算法快？KMP算法是通过分析模式串，预先计算每个位置发生不匹配的时候，可以省去重新匹配的的字符个数。整理出来发到一个next数组， 然后进行比较，这样可以避免字串的回溯，模式串中部分结果还可以复用，减少了循环次数，提高匹配效率。通俗的说就是KMP算法主要利用模式串某些字符与模式串开头位置的字符一样避免这些位置的重复比较的。例如 主串： abcabcabcabed ,模式串：abcabed。当比较到模式串'e'字符时不同的时候完全没有必要从模式串开始位置开始比较直接从模式串的'c'字符开始比较就可以了。并且主串也不用回溯了。
传统的匹配算法没有利用匹配过的信息(模式串是知道的，那么部分匹配主串也是知道的)，每次都从头开始比较，速度很慢。
先介绍前缀数组(我自己这么叫的，不知道对不对)是如何产生的。首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
来看一个例子：chi表示模式串的前i个字符组成的前缀， next[i] = j表示chi中的开始j个字符和末尾j个字符是一样的(注意下标是字符数目)，而且对于前缀chi来说，这样的j是最大值。next[i] = j的另外一个定义是：有一个含有j个字符的串，它既是chi的真前缀，又是chi的真后缀。
 规定：next[1] = next[0] = 0，这个规定不像0！=1那样，而是确实是这样子，不懂得看上面的前后缀概念。注意：next数组里并不是首尾回文串，而是前缀等于后缀，理解这个对于递推求next数组很重要哟。next[i]就是前缀数组，下面通过1个例子来看如何构造前缀数组。
 例：cacca有5个前缀，求出其对应的next数组。前缀2为ca，显然首尾没有相同的字符，next[2] = 0，前缀3为cac，显然首尾有共同的字符c，故next[3] = 1，前缀4为cacc，首尾有共同的字符c，故next[4] = 1，前缀5为cacca，首尾有共同的字符ca，故next[5] = 2。如果仔细观察，可以发现构造next[i]的时候，可以利用next[i-1]的结果。比如abcdabc，模式已求得next[7] = 3，为求next[8]，可以直接比较第4个字符和第8个字符，如果它们相等，则next[8] = next[7]+1 = 4，这是因为next[7] = 3保证了前缀ch7的末尾4个字符的前3个字符是一样的。但如果这两个字符不想等呢？那就继续迭代，利用(k=3)k = next[k]的值来求,直到k=0(next[8] = 0)或者字符相等(next[8] = k+1)。
二.算法实现

本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。