资源描述：
《模式匹配kmp算法实验步骤》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、一、问题描述模式匹配两个串。二、设计思想这种由D.E.Knuth,J.H.Morris和V.R.Pratt同吋发现的改进的模式匹配算法简称为KMP算法。注意到这是一个改进的算法，所以有必要把原來的模式匹配兑法拿出來，其实理解的关键就在这里，一般的匹配算法：intIndex(StringS,StringT,intpos)//参考《数据结构》屮的程序{i=pos;j=l;//这里的屯的笫1个元素下标是1while(i<=S.Length&&j<=T.Length){if(S[i]=T[j]){++i;++j;}eIsc{i=
2、i~j+2;j=l;}//木本*本本本*本本本*本本本(1)}if(j>T.Length)returni-T.Length;//匹配成功elsereturn0;匹配的过程非常淸晰，关键足当‘失配’的吋候税序足如何处理的？为什么要冋溯，看下面的例子：S:aaaaabababcaaaT:ababcaaaaabababcaaaababc.(.表示做一个已经失配)回溯的结果就是aaaaabababcaaaa.(babe)如果不W溯就是aaaaabababcaaaaba.be这样就漏了一个可能匹配成功的情况aaaaabababca
3、aaababc这是由T串本身的性质决定的，是因为T串本身有前后’部分匹配’的性质。如果T为abedef这样的，人没奋冋溯的必要。改进的地方也就是这里，我们从T串本身出发，事先就找准了TA身前后部分匹配的位置，那就可以改进算法。如果不用W溯，那T串下一个位置从哪甩开始呢？还是上面那个例子，T为ababc,如果c失配，那就可以往前移到aba最后一个a的位置，像这样.•…ababd…ababc->ababc这样i不川回溯，j跳到前2个位S,继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的ne
4、xt值，它是由T串本身固有决定的，与S串无关。《数据结构》上给了next值的定义：0如果j=lnext[j]={Max{k
5、l〈k〈j•(!.’pi..•pk-f-pj-k+1...pj-T1其它情况-K实它就是描述前面表述的情况，关于next[l]=O是规定的，这样规定可以使程序简单一些，如果非要定为其它的值只要不和后面的值冲突也足可以的；而那个Max是什么意思，举个例子:T:aaab...aaaab...aaab一〉aaab->aaab->aaab像这样的T,前而A身部分匹配的部分不止两个，那应该往前跳到第几个呢？最
6、近的一个，也就是说尽可能的向右滑移蛣短的长度。到这里，就实现了KMP的大部分内容，然后关键的问题是如何求next值？先看如何用它来进行匹配操作。将最前而的程序改写成：intIndex_KMP(StringS,StringT,intpos){i=pos;j=l;//这里的中的第1个素下标是1while(i<=S.Length&&j<=T.Length)if(j==O
7、
8、S[i]==T[j]){++i;++j;}//注意到这里的j==0,和++j的作用就知道为什么规定next[l]=O的好处了elsej=next[j];//
9、i不变(不回溯)，j跳动}if(j>T.Length)returni-T.Length;//匹配成功elsereturn0;}求next值，这也是整个算法成功的关键。前说过丫，next值表达的就是T申的自身部分匹配的性质，那么，我只耍将T串和T串A身来一次匹配就可以求岀来了，这里的匹配过程不是从头一个一个匹配，而是从T[l]和T[2]开始匹配，给出算法如下：voidget_noxt(StringT,int&next[]){i=l;j=0;next[l]=0;while(i<=T.Length){if(j==O
10、
11、T[i]
12、==T[j]){++i;++j;next[i]=j;/**********(2)*/}elsej=next[j];}}看这个函数非常像KMP匹配的函数！注意到(2)语川逻樹蒗盖的时候是T[i]==T[j]以及i前面的、j前面的都匹配的情况不，于足先tl增，然后记下來next[i]=j，这样每当i宥自增就会求得一个next[i],而j一定会小子等于i，于是对于已经求出来的next,可以继续求后面的next,而next[l]=0是己知，所以整个就这样递推的求出來了，方法非常巧妙。这样的改进己经是很不错了，但算法还对以改进，注
13、意到K而的匹配惜况：•••Haac.•.ci3cia.T串中的’a’和S中中的’c’失配，而’a’的next值指的还是’a’，那同样的比较还是会失配，而这样的比较是多余的，如果我事先知道，当T[i]==T[j]，那next[i]就设为nextEj],在求next值的吋候就己经比较了，这样就可以去掉这样的多余的比较。于
