简单的KMP算法

xiaoxiao2021-02-28  5

虽然题目声称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)); } } }
转载请注明原文地址: https://www.6miu.com/read-1400384.html

最新回复(0)