kmp算法实验报告

㈠ 图解KMP字符串匹配算法

kmp算法跟之前讲的bm算法思想有一定的相似性。之前提到过，bm算法中有个好后缀的概念，而在kmp中有个好前缀的概念，什么是好前缀，我们先来看下面这个例子。

观察上面这个例子，已经匹配的abcde称为好前缀，a与之后的bcde都不匹配，所以没有必要再比一次，直接滑动到e之后即可。
  那如果前缀中有互相匹配的字符呢？

观察上面这个例子，这个时候如果我们直接滑到好前缀之后，则会过度滑动，错失匹配子串。那我们如何根据好前缀来进行合理滑动？

  其实就是看当前的好前缀的前缀和后缀是否有匹配的，找到最长匹配长度，直接滑动。鉴于不止一次找最长匹配长度，我们完全可以先初始化一个数组，保存在当前好前缀情况下，最长匹配长度是多少，这时候我们的next数组就出来了。

  我们定义一个next数组，表示在当前好前缀下，好前缀的前缀和后缀的最长匹配子串长度，这个最长匹配长度表示这个子串之前已经匹配过匹配了，不需要再次进行匹配，直接从子串的下一个字符开始匹配。

 我们是否每次算next[i]时都需要每一个字符进行匹配，是否可以根据next[i - 1]进行推导以便减少不必要的比较。
  带着这个思路我们来看看下面的步骤：
  假设next[i - 1] = k - 1;
  如果modelStr[k] = modelStr[i] 则next[i]=k

如果modelStr[k] != modelStr[i]，我们是否可以直接认定next[i] = next[i - 1]？

通过上面这个例子，我们可以很清晰地看到，next[i]!=next[i-1]，那当modelStr[k]!=modelStr[i]时候，我们已知next[0],next[1]…next[i-1]，如何推导出next[i]呢？
  假设modelStr[x…i]是前缀后缀能匹配的最长后缀子串，那么最长匹配前缀子串为modelStr[0…i-x]

我们在求这个最长匹配串的时候，他的前面的次长匹配串（不包含当前i的），也就是modelStr[x…i-1]在之前应该是已经求解出来了的，因此我们只需要找到这个某一个已经求解的匹配串，假设前缀子串为modelStr[0…i-x-1],后缀子串为modelStr[x…i-1],且modelStr[i-x] == modelStr[i],这个前缀后缀子串即为次前缀子串，加上当前字符即为最长匹配前缀后缀子串。
代码实现
  首先在kmp算法中最主要的next数组，这个数组标志着截止到当前下标的最长前缀后缀匹配子串字符个数，kmp算法里面，如果某个前缀是好前缀，即与模式串前缀匹配，我们就可以利用一定的技巧不止向前滑动一个字符，具体看前面的讲解。我们提前不知道哪些是好前缀，并且匹配过程不止一次，因此我们在最开始调用一个初始化方法，初始化next数组。
  1.如果上一个字符的最长前缀子串的下一个字符==当前字符，上一个字符的最长前缀子串直接加上当前字符即可
  2.如果不等于，需要找到之前存在的最长前缀子串的下一个字符等于当前子串的，然后设置当前字符子串的最长前缀后缀子串

然后开始利用next数组进行匹配，从第一个字符开始匹配进行匹配，找到第一个不匹配的字符，这时候之前的都是匹配的，接下来先判断是否已经是完全匹配，是直接返回，不是，判断是否第一个就不匹配，是直接往后面匹配。如果有好前缀，这时候就利用到了next数组，通过next数组知道当前可以从哪个开始匹配，之前的都不用进行匹配。

㈡ 数据结构与算法——字符串匹配问题(KMP算法)

KMP算法也是比较着名的模式匹配算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 发表的一个模式匹配算法。可以大大避免重复遍历的情况。

如果使用暴风算法的话，前面五个字母完全相等，直到第六个字母 "f" 和 "x" 不相等。如下图：

T = “abcdex”
j 123456
模式串 abcdex
next[j] 011111

T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123

T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223

T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678

next数组其实就是求解字符串要回溯的位置
假设，主串S= “abcababca”;模式串T=“abcdex”，由以上分析得出next数组为011111，next数组意味着当主串与模式串不匹配时，都需要从第一个的位置重新比较。

KMP算法也是有缺陷的，比如主串S=“aaaabcde”,模式串T= “aaaaax”。next的数组就是012345；

当开始匹配时，当i= 5，j = 5时，我们发现字符"b"与字符“a”不相等，如上图，j = next[5] = 4;

由于T串的第二、三、四、五位置的字符都与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的后续字符的next[j],那么next数组为{0,0,0,0,0,5};

在求解nextVal数组的5种情况

㈢ kmp算法的优化

KMP算法是可以被进一步优化的。
我们以一个例子来说明。譬如我们给的P字符串是“abcdaabcab”，经过KMP算法，应当得到“特征向量”如下表所示： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 但是，如果此时发现p(i) == p(k），那么应当将相应的next[i]的值更改为next[k]的值。经过优化后可以得到下面的表格： 下标i 0 1 2 3 4 5 6 7 8 9 p(i) a b c d a a b c a b next[i] -1 0 0 0 0 1 1 2 3 1 优化的next[i] -1 0 0 0 -1 1 0 0 3 0 （1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。
如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个
字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].（1≤k<j）;
(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
补充一个next[]生成代码： voidgetNext(constchar*pattern,intnext[]){next[0]=-1;intk=-1,j=0;while(pattern[j]!=''){while(k!=-1&&pattern[k]!=pattern[j])k=next[k];++j;++k;if(pattern[k]==pattern[j])next[j]=next[k];elsenext[j]=k;}} PROGRAMImpl_KMP;USESCRT;CONSTMAX_STRLEN=255;VARnext:array[1..MAX_STRLEN]ofinteger;str_s,str_t:string;int_i:integer;Procereget_next(t:string);Varj,k:integer;Beginj:=1;k:=0;whilej<Length(t)dobeginif(k=0)or(t[j]=t[k])thenbeginj:=j+1;k:=k+1;next[j]:=k;endelsek:=next[k];end;End;Functionindex(s:string;t:string):integer;Vari,j:integer;Beginget_next(t);index:=0;i:=1;j:=1;while(i<=Length(s))and(j<=Length(t))dobeginif(j=0)or(s[i]=t[j])thenbegini:=i+1;j:=j+1;endelsej:=next[j];ifj>Length(t)thenindex:=i-Length(t);end;End;BEGINClrScr;{清屏，可不要}Write('s=');Readln(str_s);Write('t=');Readln(str_t);int_i:=index(str_s,str_t);ifint_i<>0thenbeginWriteln('Found''',str_t,'''in''',str_s,'''at',int_i,'.');endelseWriteln('Cannotfind''',str_t,'''in',str_s,'''.');END.index函数用于模式匹配，t是模式串，s是原串。返回模式串的位置，找不到则返回0

㈣ 计算机考研：数据结构常用算法解析(4)

第四章
KMP算法和朴素的匹配算法的关键区别就是解决了主串指针i的回溯，原理如下：
设主串S[]和模式串T[],如比较到模式串的第j个字符。 当主串指针i和模式串指针j比较时 ，说明他们前面的所有字符都已经对应相等了。而
Next[j]=k的定义是T1T2…Tk-1==Tj-k+1Tj-k+2….Tj-1且k是最大了，没有更长的了。
所以Si和Tj比较失败时Si和Tk去比较。不可能有 这种匹配的成功，因为S2S3…..Si-1= =T2T3……Tj-1,而T2T3….Tj-1是不等于T1T2….Tj-2。除非next[j]=j-1;因为next定义的是最长的。所以任何挪动小于next[j]的串的匹配都是不能成功的。直到Tnext[j]和S[i]相比是才是最早有可能成功的。
Int KMP_Index(Sstring S,Sstring T,int pos)
{
i=pos;j=1;
while(i<=S[0]&&j<=T[0])
{
If(j=0||S[i]=T[j])//j=0表示模式串已经退到起点了说明在这个位置彻底不可能了，
{ ++i; ++j; } //i必须下移,j回到1开始
Else j=next[j];
}
If(j>T[0]) return i-T[0];
Else return 0;
}
求next[j]的方法和原理
设尺肆羡k=next[j];那么T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1;
若Tj= =Tk,那么T1T2…Tk-1Tk= =Tj-k+1……Tj-2Tj-1Tj;
所以 next[j+1]=k+1=next[j]+1;且T1T2…Tk-1= =Tj-k+1……Tj-2Tj-1已经是
最长雹弊的序列，所以k+1也是next[j+1]最长的
若Tj不等于Tk,那么就需要重找了。即…..Tj-1Tj ?,
T1T2….
所以next[j+1]首先=k=next[j]; 即…..Tj-1Tj ?,
T1T2…Tk-1.
若不相等，则next[j+1]=next[k]; 即…..Tj-1Tj ?,
T1T2….Tnext[k]-1
直到找到这样的序列， 即…..Tj-1Tj ?,
T1T2 ...To
那么，next[j+1]=next[next[j]]=next[next[next[j]]]…..=o+1;
Void get_next(Sstring T,int next[])
{
i=1; next[1]=0; j=0;//i表示当前求的next
While(i
{
if(j=0 | | T[i]=T[j])
{
++i;
++j;
next[i]=j;
}
Else j=next[j];
}
}
因为 next[ ] 在匹配过程中，若T[ j ]=T[ next[j] ];那么当 S[i]不等于T[j],
S[ i]肯定也不等于T[k= next[j] ];
所以 S[i]应直接与T[next[k]]比较，而我们通陵拍过将next[j]修正
为nextval[j]=next[next[j]];这样能使比较更少。
Void get_nextval(Sstring T,int nextval[])
{
i=1; nextval[1]=0; j=0;
while(i
{
if(j=0 || T[i]= T[j])
{
++i;
++j;
if(T[i]!=T[j])
nextval[i]=j;
else
nextval[i]=next[j];
}
else
j=nextval[j];
}
空格串是指__由空格字符(ASCII值32)所组成的字符串，其长度等于 空格个数____。
在模试匹配KMP算法中所用失败函数f的定义中，为何要求p1p2……pf(j)为p1p2……pj两头匹配的真子串?且为最大真子串?
失败函数(即next)的值只取决于模式串自身，若第j个字符与主串第i个字符失配时，主串不回溯， 模式串用第k(即next[j])个字符与第i个相比，有‘p1…pk-1’=‘pj-k+1…pj-1’，为了不因模式串右移与主串第i个字符比较而丢失可能的匹配，对于上式中存在的多个k值，应取其中最大的一个。这样，因j-k最小，即模式串向右滑动的位数最小，避免因右移造成的可能匹配的丢失。
第4章节有关数据结构算法，上文中为大家作了分析，希望考生对于这些算法能够熟记于心，方便考试的应用和日后的实际操作，预祝大家都能够取得好成绩，加油!

更多详情请点击：计算机考研：数据结构常用算法解析汇总

考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/

㈤ 数据结构-串的模式匹配

串的模式匹配就是子串定位操作。给定两明亏个串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分别是串s和t的长度），在主串s中寻找子串t的过程称为模式匹配，t称为模式。如果在s中找到等于t的子串，则称匹配成功，返回t在s中的首次出现的下标位置；否则匹配失败，返回-1。

本文介绍三个串模式匹配算法，分别是简单回溯算法（Brute-Force，BF算法）、KMP算法、KMP算法的改进。

从主串s的第0个字符开始，与模式串t的第0个字符开始逐字符比较，不相同时回溯到模式串t的第0个和主串s的第1个字符，重新开始比较。以此类推，直到t的所有字符完成匹配，则匹配成功，否则匹配失败。

BF算法速度慢的原因是存在大量不必要的回溯，即在某一趟与t的匹配过程失败后，需要返回s串开始字符的下一字符重新开始比较，这对于某些模式串t来说是不必要的。例如，若s=12123123132，t=12313，在t与12 12312 3132中加粗子序列进行比较时，在 2 处发生失配，BF算法接下来将t与121 23123 132、1212 31231 32、12123 12313 2比较。由于t中的231、312与其开始的123并不相同，显然t与121 23123 132、1212 31231 32的比较是不必要的。

KMP算法就是利用模式串中与模式串开头部分子串的重复性来减少重复回溯，实现新一轮比较的直接跳转。 具体来说，KMP算法利用一个数组记录模式串中每一个字符前面有几个字符与模式串从头重复，在与s串比较失配时，直接跳转到重复子串的下一个字符继续比较，而不用跳转至模式串t的第0个字符。

算法步骤： ①计算跳转数组next。②利用KMP算法进行模式匹配。

next数组通过递推计算，即如果当前字符 t[j] 的前一个字符 t[j-1] 与其 next[j-1] 指向的字符 t[next[j-1]] 相同，意味着 t[j] 前的 next[j-1]+1 个字符与从 t[0] 到 t[next[j-1]] 的子串相同，因此 next[j]=next[j-1]+1 ；如果不相同，则递推至 t[next[j-1]] 的next值指向的字符，与 t[j-1] 比较，直到确认 t[j] 前与 t 串从头重复的数羡字符数，或者无重复字符标记为薯槐拍 0 。

注意此处的函数返回参数类型为int*，用于 返回一位数组 ，且返回的这个一位数组必须在函数中用static定义。

KMP算法进行模式匹配时，只需在回溯时将 j 指针赋值为 next[j] 。需要注意的是，若 next[j] 为 -1 ，则意味着 t[j] 前面没有与 t 从头重复的字符，且 t[j] 与 s[i] 失配，则 i 和 j 均加 1 。

考虑更特殊的模式串，还能进一步减少不必要的回溯次数。例如，s=111211112，t=11112，按照上述next的计算方式，next={-1,0,1,2,3}。当 i=3, j=3 时失配，此时 s[i]=2, t[j]=1 ，由于 next[j]=2 ，于是 j 跳转为 2 ，t=11 1 12与s=111 2 11112比较。由于 t[next[j]]=t[j] 也为 1 ，必然与 s[i]=2 不相同，显然这次回溯也不必要。

总结来说， 当失配的字符与待跳转的字符相同时，跳转一步并无意义，可再跳一步 ，即将当前字符置为跳转后字符的next值。

㈥ 算法-KMP

大一下参加学校ACM预备队集训的时候首次接触KMP算法，当时看了很多介绍文章，仍然不是很理解其实质，只是简单地套模板AC题目，待大二数据结构与算法课堂上再听老师介绍一次，才恍然大悟其实KMP也就是那么回事嘛。但当初为啥看那么多文章都没弄明白呢？正巧最近和朋友聊天时他告诉我他对KMP不是很理解，于是打算自己写一篇文章，巩固自己对KMP的认识，也希望能够帮助更多朋友理解KMP。
在开始之前，需要知晓的概念：

前缀：以原串串头为自身串头的子串，如 的前缀有：
后缀：以原串串尾为自身串尾的子串，如 的后缀有：

注意：字符串前后缀都不包括该串本身

给你一个文本串T(Text String)

再给你一个模式串P(Pattern String)

问该模式串是否在文本串中，怎么找？

一开始只好分别从文本串与模式串的串头开始逐字母比较

二者相同，再比较T串与P串的下一位

如此反复

如果一直这么顺利，两串对应位置的字符总相同，待P串中最后一个字符也匹配完毕，说明该模式串在文本串中存在，耶( •̀ ω •́ )y超开心，查找结束。但，大多数匹配过程不会如此顺利，在该例中，当匹配进行至

很明显，失配了。现在怎么办？按朴素思想，将P串相对T串整体右移一位，重新开始匹配，即

但这种算法效率无疑是十分低下的。设T串长度N，P串长度M，则朴素算法时间复杂度为O(MN)

已知的重要信息并没有被使用——已匹配的字符串前缀

在上例中，当P串最后一个字符匹配失败时，其已有包含七个字符的 前缀子串S 匹配成功

完全可以利用前缀子串S做点什么。观察到在S串

中，有相同前后缀，即下图蓝色部分

而S串各字符又与T串中对应字符相同，即有

当失配发生后，直接将P串右移四位使S串蓝色后缀部分对齐T串中蓝色前缀部分

从图中红框部分继续尝试匹配，发现再次失配。这次，已匹配成功的前缀串S为

而在该串中没有相同的前后缀，只能将P串串头移至失配处进行比较

再次失配。此时前缀串S为空串，只好如朴素算法般将P串整体右移一位，重新开始比较

匹配成功。于是又按照之前的步骤往下匹配，直至再次失配或匹配成功

后续步骤同上，不再赘述

上述示例已展现，KMP算法的精髓在于对已匹配成功的前缀串S的利用

在朴素算法中，匹配失败了，T串待匹配字符会回溯

T串原本已匹配至T[7] = 'X'，但是因为失配，需回溯到T[1] = 'b'重新开始匹配

而在KMP算法中，若P[M]与T[K]匹配失败，K不会回溯。既然匹配过程是从T[0]开始逐渐向右进行的，至T[K]失配发生时，T[0]至T[K-1]早已匹配过，何必再回溯过去重复匹配呢？于是乎，就如问题引入部分展示般

每当失配发生，我们总是去关注P串中已匹配成功的前缀串S

因为该前缀串是匹配成功的，说明在T串中必定存在与该前缀串相同的子串，记为S'

若S串中存在相同前后缀

则S'串必然也存在此相同前后缀

所以只需将P串右移四位，使得S串的该相同前缀对齐S'串的该相同后缀

再尝试比较T[7]与P[3]

至于T[7]与P[3]是否能够匹配另说（当然，本例中一看就知道没匹配上），但通过对前缀串S的利用，成功省去了P串右移一位、两位和三位后的无效匹配

继续深入思考，给定一个具体的P串，其第N位的前缀串S内容是固定的，则S是否存在相同前后缀、相同前后缀的长度与内容也是确定的。换言之，对于一个具体的P串，当其与给定T串匹配至P[N]失配，P串应右移几位再次与T串进行匹配也是确定的。我们完全可以使用一个数组记录当P[N]失配后，应当使用N之前的哪一位再来与T串进行匹配，以此提高匹配效率，记该数组为Next数组

定义Next[i] = j表示当P串中第i位失配后，跳转至P串第j位再次尝试匹配

还是以之前的P串为例，它的Next数组求出来应为

取下标5为例，其前缀串为

最长相同前后缀为

若P[5]失配，应跳转至P[1]再次尝试匹配（最长相同前缀对应P[0]，则取其后一位P[1]，若存在多位，则取最后一位的下一位），P[5]的前一个字符P[4]对应字符'a'，而P[1]前一个字符P[0]同对应字符'a'，保证了P[1]之前字符与T串中对应字符保持匹配。所以Next[5] = 1，其余下标对应Next数组值同如此求。

特别地，规定Next[0] = -1。而对于除下标0外的任意下标N，Next[N]的含义是 前N-1个已匹配成功的字符构成的前缀串S中，最长相同前后缀长度。 所以若在下标为N处匹配失败了，则应前往Next[N]所对应的下标处匹配。

具体地，以下图所示为例，P[6]与T[6]失配

而Next[6] = 2，所以使用P[2]再次尝试与T[6]进行匹配

当求出P串Next数组后，便可快速进行与T串的匹配

现在问题只剩下如何求Next数组，注意到Next数组既然只与P串本身相关，与文本串T无关，故令P串与自身匹配即可求得

考虑字符串

其Next数组应为

令其与给定文本串相匹配

当匹配进行至

失配，于是跳转至P[Next[3]] = P[1]处再次尝试匹配

再度失配，也必然失配

问题在于不该出现P[N] =P[Next[N]]

若P[N] =P[Next[N]]，则P[N]失配后使用P[Next[N]]再次尝试匹配，由于P[N] =P[Next[N]]，P[N]匹配失败，P[Next[N]]必然也失败

因此，若出现P[N] =P[Next[N]]情况，则令Next[N]=Next[Next[N]]

本例中该字符串新Next数组为

当匹配进行至

失配，于是跳转至P[Next[3]] = P[0]处再次尝试匹配

省去了之前跳转至P[1]处的无效匹配

设T串长度M，P串长度N，由于KMP算法不会回溯，分析易知时间复杂度为O(m+n)

对于P[N]，若其前缀串S含相同前后缀F，且F长度为n（n>1），Next[N]可以取1至n中任意值，为最大化匹配效率考虑，总是取最大相同前后缀以提高效率，节省时间

㈦ KMP模式匹配算法是什么

KMP模式匹配算法是一种改进算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的，因此人们称它为“克努特－莫里斯－普拉特操作”，简称KMP算法。此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程出现字符不相等时，主串指针i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指针j向右“滑动”尽可能远的一段距离后，继续进行比较。

1.KMP模式匹配算法分析回顾图4－5所示的匹配过程示例，在第三趟匹配中，当i＝7、j＝5字符比较不等时，又从i＝4、j＝1重新开始比较。然而，经仔细观察发现，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中的第4、5和6个字符必然是b、c和a（即模式串第2、第2和第4个字符）。因为模式中的第一个字符是a，因此它无须再和这三个字符进行比较，而仅需将模式向右滑动2个字符的位置进行i＝7、j＝2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动两个字符的位置继续进行i＝2、j＝1时的字符比较。由此，在整个匹配过程中，i指针没有回溯，如图1所示。

图1改进算法的模式匹配过程示意

㈧ kmp算法详解

KMP模式匹配算法
KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明[4]。
求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模式匹配算法)与朴素匹配算法类似，只是在每次匹配过程中发生某次失配时，不再单纯地把模式后移一位，而是根据当前字符的特征数来决定模式右移的位数[3]。
include "string. h"

#include<assert. h>

int KMPStrMatching(String T, String P, int. N, int startIndex)

{int lastIndex=T.strlen() -P.strlen();

if((1 astIndex- startIndex)<0)//若 startIndex过大,则无法匹配成功

return (-1);//指向P内部字符的游标

int i;//指向T内部字符的游标

int j=0;//指向P内部字符的游标

for(i= startIndex; i <T.strlen(); i++)

{while(P[j]!=T[i]&& j>0)

j=N[j-1];

if(P[j]==T[i])

j++;

if(j ==P.strlen())

return(1-j+1);//匹配成功,返回该T子串的开始位置

}

return (-1);

}