数据结构教学中KMP算法解析
数据结构教学中KMP算法解析
摘要：模式匹配是字符串的基本运算之一，也是数据结构教学中的难点之一。分析了模式匹配KMP算法以及算法中next函数的含义，给出了next函数的两种实现方法，有助于在教学实践中帮助学生更好地理解该算法。
关键词：数据结构；模式匹配；KMP算法
0引言
模式匹配（Patten Matching）是许多计算机应用领域的基础问题，在数据结构中模式匹配是字符串的基本运算之一。字符串模式匹配指的是，找出特定的模式串在一个较长的字符串中出现的位置。有两个字符串S和T，字符串S称为目标串，字符串T称为模式串，要求找出模式T在S中的首次出现的位置。一旦模式T在目标S中找到，就称发生一次匹配。有些应用可能会要求找出所有的匹配位置[1]。例如，目标串S= 'Shanghai'，模式串T= 'gha'，则匹配结果为4。
模式匹配的典型算法包括朴素匹配算法、KMP算法和BM算法等，其中KMP算法是效率较高且经典的模式匹配算法之一[2]。在数据结构教学中，由于KMP算法较难理解，课堂讲授往往很难取得好的效果。本文通过对传统的朴素匹配算法与KMP算法的比较，分析next函数的含义以及实现方法，来帮助理解KMP算法。
模式匹配的KMP算法详解
模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。
模式匹配KMP算法实验报告
实验四：KMP算法实验报告 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：
KMP算法-如何理解
对KMP算法的理解 整理者——戴红伟 字符匹配算法的现实意义：随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常重要的作用，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量。 （请同时参照课本P53～54相关内容） 1.要理解next[j]=k 中，k的含意； （1）BF算法 假设有字符串 S=S1S2......S N P=P1P2......P M 其中（M （2）KMP算法 为了解决上述的问题，KMP算法被发现。 KMP算法的思想如下。匹配过程中，出现不匹配时，S的指针不进行回朔（原地不动），将P尽可能地向后移动一定的距离，再进行匹配。 如图： （该图引用自互联网） 从上图中我们看到，当S移动到i，P到j的时候失配。这时候i不回朔，而只是将P 向前移动尽可能的距离，继续比较。 假设，P向右移动一定距离后，第k个字符P[k]和S[i]进行比较。 此时如上图，当P[j]和S[i]失配后，i不动，将P前移到K，让P[k]和S[i]继续匹配。现在的关键是K的值是多少？ 通过上图，我们发现，因为黄色部分表示已经匹配了的结果（因为是到了S[i]和P[j]的时候才失配，所以S i-j+1S i-j+2…S i-1 = P1P2…P j-1，见黄色的部分）。所以有： 1、S i-k+1S i-k+2…S i-1 = P j-k+1P j-k+2…P j-1。 所以当P前移到K时，有： 2、S i-k+1S i-k+2…S i-1 = P1P2…P k-1。 通过1，2有 P j-k+1P j-k+2…P j-1 = P1P2…P k-1。 呵呵，此时我们的任务就是求这个k值了。。。 参考：https://www.wendangku.net/doc/8a8597803.html,/2008-09/122068902261358.html 2.求出k 值 按照课本的求法就可以处理。 课本是已知前j个元素的“前缀函数值”，如何求的j+1个元素的前缀函数值。这里有一个思路要发生转变的地方，把一个模式串分成两个部分，因为我们要找k使得P j-k+1P j-k+2…P j-1= P1P2…P k-1，而这本身就是一个模式匹配问题，所以把模式串的前边部分的子串当作“新的模式串”，这样就很容易理解为什么当t k!=t j时，t1…t next[k]-1 = t j-（next[k]-1）…t j-1了。因为这时候t k匹配失败，需要进一步移动模式子串，所以移动的位置就是next[k]。 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 入 侵 检 测 试 验 实验名称:_ KMP算法实验专业班级: _ 网络工程13-01 学号:_ 姓名: 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 字符串匹配是计算机的基本任务之一。 举例来说，有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？ 许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。 我用自己的语言，试图写一篇比较好懂的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，因此按照下面的公式算出向后移动的位数： KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一.简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos 详解KMP算法中Next数组的求法 例如： 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next值0 1 1 2 2 3 1 2 next数组的求解方法是：第一位的next值为0，第二位的next 值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next 值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。 看起来很令人费解，利用上面的例子具体运算一遍。 1.前两位必定为0和1。 2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。 3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next 值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。 4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。 5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next 值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。 6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。 7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next 值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。 #define _CRT_SECURE_NO_DEPRECA TE #include s_i++; p_i++; continue; } else { if (p_i == 0) { s_i++; } else { p_i = next[p_i-1]; //取当前匹配不到之前的字符串的最大相等前缀的最后一个字符 } } for (i = 0; i < s_i - p_i; i++) { putchar(' '); } printf("%s\n",ptr); } return (p_i == plen) ? (s_i - plen) : -1;//返回第一次找到子串的下标位置 } int main() { char str[N] = { 0 }; char ptr[N] = { 0 }; int slen, plen; int next[N]; int ret; printf("请输入主串："); scanf("%s",str); printf("请输入模式串:"); scanf("%s",ptr); slen = strlen(str); plen = strlen(ptr); cal_next(ptr, next, plen); printf("\nnext:"); KMP算法是在最近这两年的软件设计师考试中才出现的。2次都是让求Next函数的序列（其实是）。先看看题吧。 （2011年下半年上午题） （2012年上半年上午题） 其实做这个题很简单，我先说说这个题里的各种概念。 给定的字符串叫做模式串T。j表示next函数的参数，其值是从1到n。而k则表示一种情况下的next函数值。p表示其中的某个字符，下标从1开始。看等式左右对应的字符是否相等。 好了，开始做题了。 首先，要把字符串填入到一个表格中：（拿第一个题为例） 将j导入next函数，即可求得， j=1时，next[0]=0； j=2时，k的取值为(1,j)的开区间，所以整数k是不存在的，那就是第三种情况，next[2]=1； j=3时，k的取值为（1，3）的开区间，k从最大的开始取值，然后带入含p的式子中验证等式是否成立，不成立k取第二大的值。现在是k=2，将k导入p的式子中得，p1=p2，即“a”=“b”，显然不成立， 舍去。k再取值就超出范围了，所以next[3]不属于第二种情况，那就是第三种了，即next[3]=1； j=4时，k的取值为（1，4）的开区间，先取k=3，将k导入p的式子中得，p1p2=p2p3，不成立。再取k=2，得p1=p3，成立。所以next[4]=2； j=5时，k的取值为（1，5）的开区间，先取k=4，将k导入p的式子中得，p1p2p3=p2p3p4，不成立。再取k=2，得p1p2=p3p4，不成立。再取k=2，得p1=p4，成立。所以next[4]=2； j=6时，k的取值为（1，6）的开区间，先取k=5，将k导入p的式子中得，p1p2p3p4=p2p3p4p5，不成立。取k=4，得p1p2p3=p3p4p5，不成立。再取k=3，将k导入p的式子中得，p1p2=p4p5，成立。所以next[4]=3； j=7时，k的取值为（1，7）的开区间，先取k=6，将k导入p的式子中得，p1p2p3p4p5=p2p3p4p5p6，不成立。再取k=5，得 p1p2p3p4=p3p4p5p6 ，不成立。再取k=4，得p1p2p3=p4p5p6 ，成立。所以next[4]=4； KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足,明确next数组需要改进之外。其中,理解算法是核心,会求数组是得分点。不用我多说,这一节内容是本章的重中之重。可能进行的考查方式是:求next和nextval 数组值,根据求得的。 KMP算法即Knuth-Morris-Pratt算法，是模式匹配的一种改进算法，因为是名字中三人同时发现的，所以称为KMP算法。因为偶然接触到有关KMP的问题，所以上网查了一下next数组和nextval数组的求法，却没有找到，只有在CSDN 的资料文件里找到了next数组的简单求法（根据书上提供的程序也可以求到，但一般在课堂讲解的时候，学生难以理解，所以希望以更容易理解的形式来讲解），那位高人说时间关系，先讲到这里，于是讲完了next数组就功成身退了。BS的同时，自己研究了下nextwal数组，发现了其中的简易规律，并写了出来，希望能对需要快速理解KMP中nextval的求法的朋友有所帮助。 int get_nextval(SString T,int &nextval[ ]){ //求模式串T的next函数修正值并存入数组nextval。 i=1; nextval[1]=0; j=0; while(i 改进的模式匹配算法的理论分析 设 T = t0 t1 … t s-1 t s t s+1 t s+2 … t s+j-1 t s+j t s+j+1 … t n-1 P = p0 p1 p2 … p j-1 p m-1． 若在匹配过程中出现了如下情况： t s t s+1t s+2… t s+j-1= p0p1p2… p j-1，(1)但t s+j ≠ p j．也就是说，在匹配过程出现了： T t0 t1 … t s-1t s t s+1t s+2… t s+j-1t s+j t s+j+1… t s+m-1 … t n-1 ‖ ‖ ‖ … ‖ ? P p0p1p2 … p j-1p j p j-1… p m-1 则本次匹配失败． 由朴素的模式匹配算法，我们需要下一趟匹配，即需要验证下式是否成立： t s+1t s+2… t s+j-1 t s+j … t s+m?= p0p1 … p j-2p j-1… p m-1(2)如果（2）式成立，则匹配成功，返回s+1；否则需要再下一趟的匹配：t s+2t s+3… t s+j-1t s+j… t s+m+1?= p0p1… p j-3p j-2 …p m-1 (2')以此类推． 下面给出两个互逆的条件 p0p1… p j-2 = p1p2 …p j-1 (3) p0p1… p j-2 ≠p1p2 …p j-1 (3')显然，这两个条件能且只能满足一个．下面并分情况讨论：【1】如果(3) 式成立，则由(1) (2) (3) 式，可以断定p0 p1 …p j-2 = t s+1 t s+2 … t s+j-1成立，即在（3）式条件下，对(2) 式的验证只需要从p j- 引记 此前一天，一位MS的朋友邀我一起去与他讨论快速排序，红黑树，字典树，B树、后缀树，包括KMP算法，唯独在讲解KMP算法的时候，言语磕磕碰碰，我想，原因有二：1、博客内的东西不常回顾，忘了不少；2、便是我对KMP算法的理解还不够彻底，自不用说讲解自如，运用自如了。所以，特再写本篇文章。由于此前，个人已经写过关于KMP算法的两篇文章，所以，本文名为：KMP算法之总结篇。 本文分为如下六个部分： 1. 第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度，并两相对照各 自的匹配原理； 2. 第二部分、通过我此前第二篇文章的引用，用图从头到尾详细阐述KMP算法中的 next数组求法，并运用求得的next数组写出KMP算法的源码； 3. 第三部分、KMP算法的两种实现，代码实现一是根据本人关于KMP算法的第二篇文 章所写，代码实现二是根据本人的关于KMP算法的第一篇文章所写； 4. 第四部分、测试，分别对第三部分的两种实现中next数组的求法进行测试，挖掘其 区别之所在； 5. 第五部分、KMP完整准确源码，给出KMP算法的准确的完整源码； 6. 第六步份、一眼看出字符串的next数组各值，通过几个例子，让读者能根据字符串 本身一眼判断出其next数组各值。 力求让此文彻底让读者洞穿此KMP算法，所有原理，来龙去脉，让读者搞个通通透透（注意，本文中第二部分及第三部分的代码实现一的字符串下标i 从0开始计算，其它部分如第三部分的代码实现二，第五部分，和第六部分的字符串下标i 皆是从1开始的）。 在看本文之前，你心中如若对前缀和后缀这个两个概念有自己的理解，便最好了。有些东西比如此KMP算法需要我们反复思考，反复求解才行。个人写的关于KMP算法的第二篇文章为：六（续）、从KMP算法一步一步谈到BM算法；第一篇为：六、教你初步了解KMP算法、updated（文末链接）。ok，若有任何问题，恳请不吝指正。多谢。 第一部分、KMP算法初解 1、普通字符串匹配BF算法与KMP算法的时间复杂度比较 这里有两种KMP算法的详解~大家可以参考 KMP字符串模式匹配详解KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。 一．简单匹配算法 先来看一个简单匹配算法的函数： int Index_BF ( char S [ ], char T [ ], int pos ) { /* 若串S 中从第pos(S 的下标0≤pos j=0 起比较S[i+j] 与T[j]，若相等，则在主串S 中存在以i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即i 增1，而j 退回至0，重新开始新一轮的匹配。 例如：在串S=”abcabcabdabba”中查找T=” abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1] 和T[1]是否相等…我们发现一直比较到S[5] 和T[5]才不等。如图： 当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S 下标增1,然后再次比较。如图： 这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图： 这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图： 模式匹配的KMP算法研究 学生姓名：黄飞指导老师：罗心 摘要在计算机科学领域，串的模式匹配<以下简称为串匹配）算法一直都是研究焦点之一。在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病 毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。串匹配就是在主串中 查找模式串的一个或所有出现。在本文中主串表示为S=s1s2s3…sn，模式串表示为 T=t1t2…tm。串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配 算法有BF算法、KMP算法、BM算法及一些改进算法。本文主要在精确匹配方面对KMP 算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。 关键字：模式匹配；主串；模式串；KMP算法 Research and Analysis of KMP Pattern Matching Algorithm Student:Huangfei Teacher:Luoxin Abstract In computer science,String pattern matching(Hereinafter referred to as the string matching>algorithmis always the focus of the study.In the spell check, language translation, data compression, search engine, the network intrusion detection system, a computer virus signature matching DNA模式匹配KMP算法实验步骤
KMP算法实验
字符串匹配的KMP算法
(完整word版)KMP算法详解
详解KMP算法中Next数组的求法
KMP算法源码
KMP算法考题
KMP算法演算过程(讲述内容)
KMP算法的理论推导
kmp算法详解
大学课件-KMP算法
模式匹配KMP算法研究报告