广告网站建设公司,封面型网页网站有哪些内容,自己使用原生php做网站性能,投资网站策划【经典算法】——KMP#xff0c;深入讲解next数组的求解 前言 之前对kmp算法虽然了解它的原理#xff0c;即求出P0Pi的最大相同前后缀长度k#xff1b;但是问题在于如何求出这个最大前后缀长度呢#xff1f;我觉得网上很多帖子都说的不是很清楚#xff0c;总感觉没有把… 【经典算法】——KMP深入讲解next数组的求解 前言 之前对kmp算法虽然了解它的原理即求出P0···Pi的最大相同前后缀长度k但是问题在于如何求出这个最大前后缀长度呢我觉得网上很多帖子都说的不是很清楚总感觉没有把那层纸戳破后来翻看算法导论32章 字符串匹配虽然讲到了对前后缀计算的正确性但是大量的推理证明不大好理解没有与程序结合起来讲。今天我在这里讲一讲我的一些理解希望大家多多指教如果有不清楚的或错误的请给我留言。 1.kmp算法的原理 本部分内容转自http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 字符串匹配是计算机的基本任务之一。 举例来说有一个字符串BBC ABCDAB ABCDABCDABDE我想知道里面是否包含另一个字符串ABCDABD 许多算法可以完成这个任务Knuth-Morris-Pratt算法简称KMP是最常用的之一。它以三个发明者命名起头的那个K就是著名科学家Donald Knuth。 这种算法不太容易理解网上有很多解释但读起来都很费劲。直到读到Jake Boxer的文章我才真正理解这种算法。下面我用自己的语言试图写一篇比较好懂的KMP算法解释。 1. 首先字符串BBC ABCDAB ABCDABCDABDE的第一个字符与搜索词ABCDABD的第一个字符进行比较。因为B与A不匹配所以搜索词后移一位。 2. 因为B与A不匹配搜索词再往后移。 3. 就这样直到字符串有一个字符与搜索词的第一个字符相同为止。 4. 接着比较字符串和搜索词的下一个字符还是相同。 5. 直到字符串有一个字符与搜索词对应的字符不相同为止。 6. 这时最自然的反应是将搜索词整个后移一位再从头逐个比较。这样做虽然可行但是效率很差因为你要把搜索位置移到已经比较过的位置重比一遍。 7. 一个基本事实是当空格与D不匹配时你其实知道前面六个字符是ABCDAB。KMP算法的想法是设法利用这个已知信息不要把搜索位置移回已经比较过的位置继续把它向后移这样就提高了效率。 8. 怎么做到这一点呢可以针对搜索词算出一张《部分匹配表》Partial Match Table。这张表是如何产生的后面再介绍这里只要会用就可以了。 9. 已知空格与D不匹配时前面六个字符ABCDAB是匹配的。查表可知最后一个匹配字符B对应的部分匹配值为2因此按照下面的公式算出向后移动的位数 移动位数 已匹配的字符数 - 对应的部分匹配值 因为 6 - 2 等于4所以将搜索词向后移动4位。 10. 因为空格与不匹配搜索词还要继续往后移。这时已匹配的字符数为2AB对应的部分匹配值为0。所以移动位数 2 - 0结果为 2于是将搜索词向后移2位。 11. 因为空格与A不匹配继续后移一位。 12. 逐位比较直到发现C与D不匹配。于是移动位数 6 - 2继续将搜索词向后移动4位。 13. 逐位比较直到搜索词的最后一位发现完全匹配于是搜索完成。如果还要继续搜索即找出全部匹配移动位数 7 - 0再将搜索词向后移动7位这里就不再重复了。 14. 下面介绍《部分匹配表》是如何产生的。 首先要了解两个概念前缀和后缀。 前缀指除了最后一个字符以外一个字符串的全部头部组合后缀指除了第一个字符以外一个字符串的全部尾部组合。 15. 部分匹配值就是前缀和后缀的最长的共有元素的长度。以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。 16. 部分匹配的实质是有时候字符串头部和尾部会有重复。比如ABCDAB之中有两个AB那么它的部分匹配值就是2AB的长度。搜索词移动的时候第一个AB向后移动4位字符串长度-部分匹配值就可以来到第二个AB的位置。 2.next数组的求解思路 通过上文完全可以对kmp算法的原理有个清晰的了解那么下一步就是编程实现了其中最重要的就是如何根据待匹配的模版字符串求出对应每一位的最大相同前后缀的长度。我先给出我的代码 1 void makeNext(const char P[],int next[])2 {3 int q,k;//q:模版字符串下标k:最大前后缀长度4 int m strlen(P);//模版字符串长度5 next[0] 0;//模版字符串的第一个字符的最大前后缀长度为06 for (q 1,k 0; q m; q)//for循环从第二个字符开始依次计算每一个字符对应的next值7 {8 while(k 0 P[q] ! P[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k9 k next[k-1]; //不理解没关系看下面的分析这个while循环是整段代码的精髓所在确实不好理解
10 if (P[q] P[k])//如果相等那么最大相同前后缀长度加1
11 {
12 k;
13 }
14 next[q] k;
15 }
16 } 现在我着重讲解一下while循环所做的工作 已知前一步计算时最大相同的前后缀长度为kk0即P[0]···P[k-1] 此时比较第k项P[k]与P[q],如图1所示 如果P[K]等于P[q]那么很简单跳出while循环; 关键关键有木有关键如果不等呢那么我们应该利用已经得到的next[0]···next[k-1]来求P[0]···P[k-1]这个子串中最大相同前后缀可能有同学要问了——为什么要求P[0]···P[k-1]的最大相同前后缀呢是啊为什么呢 原因在于P[k]已经和P[q]失配了而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同看来P[0]···P[k-1]这么长的子串是用不了了那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]···P[j-1](jnext[k-1])看看它的下一项P[j]是否能和P[q]匹配。如图2所示 附代码 1 #includestdio.h2 #includestring.h3 void makeNext(const char P[],int next[])4 {5 int q,k;6 int m strlen(P);7 next[0] 0;8 for (q 1,k 0; q m; q)9 {
10 while(k 0 P[q] ! P[k])
11 k next[k-1];
12 if (P[q] P[k])
13 {
14 k;
15 }
16 next[q] k;
17 }
18 }
19
20 int kmp(const char T[],const char P[],int next[])
21 {
22 int n,m;
23 int i,q;
24 n strlen(T);
25 m strlen(P);
26 makeNext(P,next);
27 for (i 0,q 0; i n; i)
28 {
29 while(q 0 P[q] ! T[i])
30 q next[q-1];
31 if (P[q] T[i])
32 {
33 q;
34 }
35 if (q m)
36 {
37 printf(Pattern occurs with shift:%d\n,(i-m1));
38 }
39 }
40 }
41
42 int main()
43 {
44 int i;
45 int next[20]{0};
46 char T[] ababxbababcadfdsss;
47 char P[] abcdabd;
48 printf(%s\n,T);
49 printf(%s\n,P );
50 // makeNext(P,next);
51 kmp(T,P,next);
52 for (i 0; i strlen(P); i)
53 {
54 printf(%d ,next[i]);
55 }
56 printf(\n);
57
58 return 0;
59 } 3.kmp的优化 待续。。。。 【经典算法】——KMP深入讲解next数组的求解 前言 之前对kmp算法虽然了解它的原理即求出P0···Pi的最大相同前后缀长度k但是问题在于如何求出这个最大前后缀长度呢我觉得网上很多帖子都说的不是很清楚总感觉没有把那层纸戳破后来翻看算法导论32章 字符串匹配虽然讲到了对前后缀计算的正确性但是大量的推理证明不大好理解没有与程序结合起来讲。今天我在这里讲一讲我的一些理解希望大家多多指教如果有不清楚的或错误的请给我留言。 1.kmp算法的原理 本部分内容转自http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html 字符串匹配是计算机的基本任务之一。 举例来说有一个字符串BBC ABCDAB ABCDABCDABDE我想知道里面是否包含另一个字符串ABCDABD 许多算法可以完成这个任务Knuth-Morris-Pratt算法简称KMP是最常用的之一。它以三个发明者命名起头的那个K就是著名科学家Donald Knuth。 这种算法不太容易理解网上有很多解释但读起来都很费劲。直到读到Jake Boxer的文章我才真正理解这种算法。下面我用自己的语言试图写一篇比较好懂的KMP算法解释。 1. 首先字符串BBC ABCDAB ABCDABCDABDE的第一个字符与搜索词ABCDABD的第一个字符进行比较。因为B与A不匹配所以搜索词后移一位。 2. 因为B与A不匹配搜索词再往后移。 3. 就这样直到字符串有一个字符与搜索词的第一个字符相同为止。 4. 接着比较字符串和搜索词的下一个字符还是相同。 5. 直到字符串有一个字符与搜索词对应的字符不相同为止。 6. 这时最自然的反应是将搜索词整个后移一位再从头逐个比较。这样做虽然可行但是效率很差因为你要把搜索位置移到已经比较过的位置重比一遍。 7. 一个基本事实是当空格与D不匹配时你其实知道前面六个字符是ABCDAB。KMP算法的想法是设法利用这个已知信息不要把搜索位置移回已经比较过的位置继续把它向后移这样就提高了效率。 8. 怎么做到这一点呢可以针对搜索词算出一张《部分匹配表》Partial Match Table。这张表是如何产生的后面再介绍这里只要会用就可以了。 9. 已知空格与D不匹配时前面六个字符ABCDAB是匹配的。查表可知最后一个匹配字符B对应的部分匹配值为2因此按照下面的公式算出向后移动的位数 移动位数 已匹配的字符数 - 对应的部分匹配值 因为 6 - 2 等于4所以将搜索词向后移动4位。 10. 因为空格与不匹配搜索词还要继续往后移。这时已匹配的字符数为2AB对应的部分匹配值为0。所以移动位数 2 - 0结果为 2于是将搜索词向后移2位。 11. 因为空格与A不匹配继续后移一位。 12. 逐位比较直到发现C与D不匹配。于是移动位数 6 - 2继续将搜索词向后移动4位。 13. 逐位比较直到搜索词的最后一位发现完全匹配于是搜索完成。如果还要继续搜索即找出全部匹配移动位数 7 - 0再将搜索词向后移动7位这里就不再重复了。 14. 下面介绍《部分匹配表》是如何产生的。 首先要了解两个概念前缀和后缀。 前缀指除了最后一个字符以外一个字符串的全部头部组合后缀指除了第一个字符以外一个字符串的全部尾部组合。 15. 部分匹配值就是前缀和后缀的最长的共有元素的长度。以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。 16. 部分匹配的实质是有时候字符串头部和尾部会有重复。比如ABCDAB之中有两个AB那么它的部分匹配值就是2AB的长度。搜索词移动的时候第一个AB向后移动4位字符串长度-部分匹配值就可以来到第二个AB的位置。 2.next数组的求解思路 通过上文完全可以对kmp算法的原理有个清晰的了解那么下一步就是编程实现了其中最重要的就是如何根据待匹配的模版字符串求出对应每一位的最大相同前后缀的长度。我先给出我的代码 1 void makeNext(const char P[],int next[])2 {3 int q,k;//q:模版字符串下标k:最大前后缀长度4 int m strlen(P);//模版字符串长度5 next[0] 0;//模版字符串的第一个字符的最大前后缀长度为06 for (q 1,k 0; q m; q)//for循环从第二个字符开始依次计算每一个字符对应的next值7 {8 while(k 0 P[q] ! P[k])//递归的求出P[0]···P[q]的最大的相同的前后缀长度k9 k next[k-1]; //不理解没关系看下面的分析这个while循环是整段代码的精髓所在确实不好理解
10 if (P[q] P[k])//如果相等那么最大相同前后缀长度加1
11 {
12 k;
13 }
14 next[q] k;
15 }
16 } 现在我着重讲解一下while循环所做的工作 已知前一步计算时最大相同的前后缀长度为kk0即P[0]···P[k-1] 此时比较第k项P[k]与P[q],如图1所示 如果P[K]等于P[q]那么很简单跳出while循环; 关键关键有木有关键如果不等呢那么我们应该利用已经得到的next[0]···next[k-1]来求P[0]···P[k-1]这个子串中最大相同前后缀可能有同学要问了——为什么要求P[0]···P[k-1]的最大相同前后缀呢是啊为什么呢 原因在于P[k]已经和P[q]失配了而且P[q-k] ··· P[q-1]又与P[0] ···P[k-1]相同看来P[0]···P[k-1]这么长的子串是用不了了那么我要找个同样也是P[0]打头、P[k-1]结尾的子串即P[0]···P[j-1](jnext[k-1])看看它的下一项P[j]是否能和P[q]匹配。如图2所示 附代码 1 #includestdio.h2 #includestring.h3 void makeNext(const char P[],int next[])4 {5 int q,k;6 int m strlen(P);7 next[0] 0;8 for (q 1,k 0; q m; q)9 {
10 while(k 0 P[q] ! P[k])
11 k next[k-1];
12 if (P[q] P[k])
13 {
14 k;
15 }
16 next[q] k;
17 }
18 }
19
20 int kmp(const char T[],const char P[],int next[])
21 {
22 int n,m;
23 int i,q;
24 n strlen(T);
25 m strlen(P);
26 makeNext(P,next);
27 for (i 0,q 0; i n; i)
28 {
29 while(q 0 P[q] ! T[i])
30 q next[q-1];
31 if (P[q] T[i])
32 {
33 q;
34 }
35 if (q m)
36 {
37 printf(Pattern occurs with shift:%d\n,(i-m1));
38 }
39 }
40 }
41
42 int main()
43 {
44 int i;
45 int next[20]{0};
46 char T[] ababxbababcadfdsss;
47 char P[] abcdabd;
48 printf(%s\n,T);
49 printf(%s\n,P );
50 // makeNext(P,next);
51 kmp(T,P,next);
52 for (i 0; i strlen(P); i)
53 {
54 printf(%d ,next[i]);
55 }
56 printf(\n);
57
58 return 0;
59 } 3.kmp的优化 待续。。。。
