下载文档原格式
数据结构课程设计使用kmp算法实现字符串的模式匹配问题本次数据结构课程设计将使用KMP算法实现字符串的模式匹配问题。
KMP算法，全称是Knuth-Morris-Pratt算法，它是一种字符串匹配算法，可以用来解决"在一个文本串S内查找一个模式串P的出现位置"这样的问题。
在字符串匹配问题中，最简单朴素的算法就是暴力匹配，它的时间复杂度是O(m*n)，其中m为模式串的长度，n为文本串的长度。
而KMP算法通过预处理模式串，使得可以在O(n)的时间内查找出文本串中的所有模式串出现的位置。
具体来说，KMP算法的核心思想是：当匹配失败时，尽可能地跳过已经匹配的部分，从而实现快速匹配。
而跳过已经匹配的部分的方法则是通过对模式串进行预处理，得到一个next数组，next数组中存放的是当当前字符匹配失败后，应该跳过已匹配的字符数量，从而能够加速匹配。
下面是使用KMP算法实现字符串模式匹配的主要步骤：1.预处理模式串，得到next数组2.在文本串S中，按照模式串P进行匹配，记录匹配成功的位置3.如果匹配成功，则将模式串和文本串移到下一个位置继续匹配4.如果匹配失败，则根据next数组跳过已匹配的字符数量，从而加速匹配本次课程设计的具体任务包括：1.了解KMP算法的基本原理和实现方法2.使用C++语言实现KMP算法，可以参考以下代码:```c++#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int N = 1e6 + 10;char p[N], s[N];int ne[N];int main(){cin >> s + 1 >> p + 1;int n = strlen(s + 1), m = strlen(p + 1);//预处理next数组for(int i = 2, j = 0; i <= m; i++){while(j && p[i] != p[j + 1]) j = ne[j];if(p[i] == p[j + 1]) j++;ne[i] = j;}//匹配过程for(int i = 1, j = 0; i <= n; i++){while(j && s[i] != p[j+1]) j = ne[j];if(s[i] == p[j+1]) j++;if(j == m){printf("%d ", i - m);j = ne[j];}}return 0;}```3.使用自己设计的测试数据对代码进行测试，并对运行结果进行分析和总结。
模式匹配的KMP算法研究学生姓名：黄飞指导老师：罗心摘要在计算机科学领域，串的模式匹配<以下简称为串匹配）算法一直都是研究焦点之一。
在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中，都需要进行串匹配。
串匹配就是在主串中查找模式串的一个或所有出现。
在本文中主串表示为S=s1s2s3…sn，模式串表示为T=t1t2…tm。
串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改进算法。
本文主要在精确匹配方面对KMP算法进行了讨论并对它做一些改进以及利用改进的KMP来实现多次模式匹配。
关键字：模式匹配；主串；模式串；KMP算法Research and Analysis of KMP Pattern MatchingAlgorithmStudent:Huangfei Teacher:LuoxinAbstract In computer science,String pattern matching(Hereinafter referred to as the string matching>algorithmis always the focus of the study.In thespell check, language translation, data compression, search engine, thenetwork intrusion detection system, a computer virus signature matching DNAsequences and the application in the match,matched to string matching.String matching is in search of a string of pattern or all appear.In this paper, the string is S = s1s2s3... Sn, string pattern for T = t1t2... tm.String matching way can be divided from the accurate matching, fuzzy matching, parallel matching etc., the famous matching algorithms are KMP algorithm, BF algorithm, the algorithm and some BM algorithm.This paper in precise KMP algorithm for matching aspects are discussed and some improvement on it and using the improved KMP to realize the multiple pattern matching.Key words: pattern matching, The string。
实验四：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个元素下标是1while(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:ababcaaaaabababcaaaababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babc)如果不回溯就是aaaaabababcaaaaba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaaababc这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。
如果T为a bcdef这样的，大没有回溯的必要。
改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。
如果不用回溯，那T串下一个位置从哪里开始呢？还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：...ababd...ababc->ababc这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。
kmp算法实验报告篇一：模式匹配KMP算法实验报告实验四：KMP算法实验报告一、问题描述模式匹配两个串。
二、设计思想这种由,注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：int Index(String S,String T,int pos)//参考《数据结构》中的程序 {i=pos;j=1;//这里的串的第1个元素下标是1while(i {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:ababcaaaaabababcaaaababc.(.表示前一个已经失配)回溯的结果就是aaaaabababcaaaa.(babc)如果不回溯就是aaaaabababcaaaaba.bc这样就漏了一个可能匹配成功的情况aaaaabababcaaaababc这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。
如果T为abcdef这样的，大没有回溯的必要。
改进的地方也就是这里，我们从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=1next[j]={Max{k|1 1其它情况其实它就是描述前面表述的情况，关于next[1]=0是规定的，这样规定可以使程序简单一些，如果非要定为其它的值只要不和后面的值冲突也是可以的；而那个Max是什么意思，举个例子：T:aaab...aaaab...aaab->aaab->aaab->aaab像这样的T，前面自身部分匹配的部分不止两个，那应该往前跳到第几个呢？最近的一个，也就是说尽可能的向右滑移最短的长度。
kmp算法生活例题KMP算法是一种用于解决字符串匹配问题的算法，可以在O(n+m)的时间复杂度内完成匹配操作，其中n为原始字符串长度，m为匹配字符串长度。
KMP算法的应用非常广泛，在生活中我们可以通过KMP算法来解决一些实际问题。
例如，在生活中我们经常需要查找一些字符串在一本书籍或者文件中的出现次数。
如果使用暴力匹配算法来解决这个问题，时间复杂度将会是O(n*m)，其中n为书籍或文件的长度，m为要匹配的字符串长度。
如果书籍或文件非常大，将导致耗费大量时间。
而使用KMP算法，可以大大提高查找效率。
首先，我们需要对要匹配的字符串进行预处理，构建一个辅助数组next，用于记录每个字符的最长可匹配前缀的后缀长度。
然后，根据这个next数组，结合主串和模式串的指针进行匹配。
具体的过程如下：1. 预处理：根据要匹配的字符串生成辅助数组next。
假设要匹配的字符串为pattern，next数组的长度为m，i为当前字符的索引位置。
- 初始化next[0] = -1，next[1] = 0；-令j=0；-循环执行以下步骤，直到i等于m-1：- 如果j等于-1或者pattern[i]等于pattern[j]，则令i和j分别加1；- 如果pattern[i]等于pattern[j]，则next[i+1] = j+1；- 否则next[i+1] = next[j]+1；- 否则，令j = next[j]；- 返回next数组。
2. 匹配：通过next数组对主串text和模式串pattern进行匹配。
- 初始化text和pattern的指针分别为i和j，令i = 0，j = 0；-循环执行以下步骤：- 如果j等于-1或者text[i]等于pattern[j]，则令i和j分别加1；- 否则，令j = next[j]；- 如果j等于m，表示匹配成功，更新匹配次数，并且令j =next[j]；-返回匹配次数。
接下来，我们通过一个生活例题来说明KMP算法的应用。
天津市大学软件学院实验报告课程名称：串匹配算法实验姓名：***学号：**********班级：业务1114串匹配问题一、实验题目：给定一个主串，在该主串中查找并定位任意给定字符串。
二、实验目的：(1)深刻理解并掌握蛮力法的设计思想；(2)提高应用蛮力法设计算法的技能；(3)理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。
三、实验分析：串匹配问题的BF算法1 在串S中和串T中设比较的下标i=1和j=1;2 循环直到S中所剩字符个数小于T的长度或T中所有字符均比较完2.1 k=i2.2 如果S[i]=T[j],则比较S和T的下一字符,否则2.2 将i和j回溯(i=k+1; j=1)3 如果T中所有字符均比较完,则匹配成功,返回k否则匹配失败,返回0时间复杂度：设匹配成功发生在si处，则在i-1趟不成功的匹配中比较了（i-1）m次，第i趟成功匹配共比较了m次，所以总共比较了i m次，因此平均比较次数是：pi(i m)=(i m)=一般情况下，m<<n,因此最坏情况下时间复杂度是Ο(n m)。
串匹配问题的KMP算法实现过程：在串S和串T中高比较的起始下标i和j；循环直到S中所剩字符小于T的长度或T的所有字符均比较完（如果S[i]=T[j],则继续比较S和T的下一个字符；否则将j向右滑动到next[j]位置，即j=next[j];如果j=0,则将i和j分别+1，准备下趟比较，至于其中的next在此不作详细讲解）；如果T中所有字符均比较完，则匹配成功，返回匹配的起始下标；否则匹配失败，返回0。
时间复杂度：Ο(n m)，当m<<n时，KMP算法的时间复杂性是Ο(n)。
四、实验所用语言和运行环境C++，运行环境Microsoft Visual C++ 6.0五、实验过程的原始记录BF算法程序代码#include<iostream.h>#include<string>void main(){cout<<"请输入主串并且以0和回车结束"<<endl;char s[100];char t[100];for(int m=0;m<100;m++){cin>>s[m];if(s[m]=='0'){s[m]='\0';break;}}cout<<"您输入的主串为：";for(int o=0;o<strlen(s);++o){cout<<s[o];}cout<<endl;cout<<"主串长度：";cout<<strlen(s);cout<<endl<<endl;cout<<"请输入子串并且以0和回车结束"<<endl;for(int n=0;n<100;n++){cin>>t[n];if(t[n]=='0'){t[n]='\0';break;}}cout<<"您输入的子串为：";for(int a=0;a<strlen(t);++a){cout<<t[a];}cout<<endl;cout<<"子串长度：";cout<<strlen(t);cout<<endl;cout<<endl<<"++++++++BF算法++++++++"<<endl;int i,j,k,y=0;for(i=0;i<strlen(s)-strlen(t)+1;){k=i;for(j=0;j<strlen(t);)if(s[i]==t[j]){if(j==strlen(t)-1){cout<<"找到了相同的字串：";cout<<"位置在主串的第"<<i-j+1<<"的位置上";cout<<endl;y=1;break;}++i;++j;}else{j=0;break;}}i=k+1;if(y==1)break;}if(i==strlen(s)-strlen(t)+1&&j!=strlen(t)-1){cout<<"没有找到可以匹配的子串"<<endl;}}程序执行结果：查找到了子串没有查找到子串程序代码#include<iostream.h>#include<string>//前缀函数值,用于KMP算法int GETNEXT(char t[],int b){int NEXT[10];NEXT[0]=-1;int j,k;j=0;k=-1;while(j<strlen(t)){if ((k==-1)||(t[j]==t[k])){j++;k++;NEXT[j]=k;}else k=NEXT[k];}b=NEXT[b];return b;}int KMP(char s[],char t[]){int a=0;int b=0;int m,n;m=strlen(s); //主串长度n=strlen(t); //子串长度cout<<endl<<"+++++++++KMP算法++++++++++++"<<endl;while(a<=m-n){while(s[a]==t[b]&&b!=n){a++;b++;}if(b==n){cout<<"找到了相应的子串位置在主串："<<a-b+1<<endl;return 0;}b=GETNEXT(t,b);a=a-b;if(b==-1) b++;}cout<<"没有找到匹配的子串！"<<endl;return 0;}void main(){cout<<"请输入主串并且以0和回车结束"<<endl;char s[100];char t[100];for(int m=0;m<100;m++){cin>>s[m];if(s[m]=='0'){s[m]='\0';break;}}cout<<"您输入的主串为：";for(int o=0;o<strlen(s);++o){cout<<s[o];}cout<<endl;cout<<"主串长度：";cout<<strlen(s);cout<<endl<<endl;cout<<"请输入子串并且以0和回车结束"<<endl;for(int n=0;n<100;n++){cin>>t[n];if(t[n]=='0'){t[n]='\0';break;}}cout<<"您输入的子串为：";for(int a=0;a<strlen(t);++a){cout<<t[a];}cout<<endl;cout<<"子串长度：";cout<<strlen(t);cout<<endl;KMP(s,t);}程序执行结果：查找到子串没有查到子串。
数据结构实验报告学院软件学院年级2009级班级班学号姓名2010 年 3 月24 日目录一、实验内容 (1)二、实验过程 (X)三、实验结果 (X)一、实验内容：1、实验题目：KMP算法2、实验要求：实现教材中字串比较kmp算法，比较模式串abaabcac与主串acabaabaabcacaabc。
3、实验目标：了解并掌握串的类型定义和基本操作，并在此基础上实现kmp算法。
了解kmp算法的基本原理和next函数的使用。
二、实验过程：1、任务分配2、设计思想（1）KMP算法：在模式匹配中，每当一趟匹配过程出现字符比较不等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右滑动尽可能远的一段距离之后，继续进行比较。
（2）next函数：看成一个模式匹配问题，整个模式串既是主串又是模式串，可仿照KMP算法。
3、需求分析(1) 输入的形式和输入值的范围：输入主串S,模式串T，位置pos(2) 输出的形式：模式串在主串中开始匹配的位置i(3) 程序所能达到的功能：利用kmp算法完成模式串和主串的模式匹配，并输出模式串在主串中开始匹配的位置(4) 测试数据：S=acabaabaabcacaabcT=abaabcacPos=64、概要设计1).抽象数据类型Class String()定义字符串Int StrLength()返回串的长度V oid get_next()求模式串T的next函数值并存入nextint kmp()利用模式串T的next函数求出T在主串S中第pos个字符之后的位置的KMP算法2).算法a.kmp算法模块：实现主串和模式串的模式匹配b.next函数模块：实现模式串自身的模式匹配，并存入nxet函数中c.接收处理命令（初始化数据）5、详细设计程序代码（含注释）6、调试分析（1）调试中的问题分析：a.（2）算法的时空分析：在利用简单的Index()函数进行模式匹配时，虽然易于理解，但是该算法效率很低。
