简单的KMP算法

虽然题目声称KMP简单，但只是对于理解了的人而言的，但是对于还没有理解的人来说，KMP算法确实是非常难的，但是不要紧，我相信通过我的介绍你会理解的，但是个人认为，不论什么比较难理解的算法，如果直接给你讲，即使讲的方法再简单，但是你没有去自己思考，那也是理解不了的，就像做一道特别难的数学题，你想了几个小时还是没有做出来，但是这时候当别人给你说的时候，你可能会豁然开朗，这是因为你前面几个小时的思考起到的关键性作用，所以对于任何算法你都要先试图自己去思考单独，最后实在想不出来再去看看别人的想法，你会更加容易理解，好了，废话不多说，下面就来详细说说KMP算法：

(一)前缀和后缀 ，这个不用说太多解释，直接上一个人例题你就会明白,

（1）以”ABCDABD”为例，”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]

（2）又如：字符串ABCAB 前缀：{A， AB， ABC， ABCA}后缀：{BCAB， CAB， AB， B}

前缀与后缀的作用其实就是找到相同的元素长度，在进行比较的字符串的时候，可以直接进行相同元素的比较，而不是一步一步返回来比较，因此提高了匹配效率。

（二）知道了前缀和后缀，我们就来看看如何利用他们进行字符串的匹配,以字符串”BBCABCDABABCDABCDABDE”和”ABCDABD”来进行匹配。

(1)首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符比较，不匹配，移到下一个字符 （2）不匹配，以一个字符比较 (3)移到A时候，这时候匹配了 (4)此时直到D所对应的不匹配了，这时候该怎么办呢, （5）这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。 (6)但是你感觉这样好吗？肯定是不好的，那该怎么办呢，这时候前缀和后缀就派上用场了，我们不需要直接从头比较，我们只要直接比较相同元素就可以了，因为这时候又重新达到了一个匹配。

(三)由于需要每次匹配需要一个指示位置，这时候就需要一个next数组，直到着当不匹配时候，该如何比较：以上面为例子：

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例， － “A”的前缀和后缀都为空集，共有元素的长度为0； －　“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0； －　“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0； －　“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0； －　“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1； －　“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2； －　“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

(四)代码

（1）求next

void makeNext(const char P[],int next[]) { int q,k;//q:模版字符串下标；k最大前后缀长度 int m = strlen(P); next[0] = 0; for (q = 1,k = 0; q < m; ++q)//for循环，从第二个字符开始，依次计算每一个字符对 应的next值 { while(k > 0 && P[q] != P[k]) k = next[k-1]; if (P[q] == P[k]) { k++; } next[q] = k; } }

(2）求解匹配

int kmp(const char T[],const char P[],int next[]) { int n,m; int i,q; n = strlen(T); m = strlen(P); makeNext(P,next); for (i = 0,q = 0; i < n; ++i) { while(q > 0 && P[q] != T[i]) q = next[q-1]; if (P[q] == T[i]) { q++; } if (q == m) { printf("Pattern occurs with shift:%d\n",(i-m+1)); } } }