资源描述：
《基于MATLAB地数据结构与算法_KMP.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、基于MATLAB 《数据结构与算法》延边大学信息管理专业(13级)崔基哲KMP模式匹配算法MATLAB编程之基础算法3串的模式匹配算法一、基本概念1、模式匹配（定位）设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。2、算法目的确定主串中所含子串第一次出现的位置（定位）3、算法种类KMP算法KMP模式匹配算法它是：在一个长字符串中匹配一个短子串的无回溯算法。定义s:模式串,m:模式串的长度text:要匹配的字符串,n:
2、text的长度设text:x1,x2,…xn,s:a1,a2,…am,则当存在i使xi+k=ak(k=1,2,…m)时，认为text与模式串匹配，当然text也可能与模式串有多处匹配例如：text:abcabca,s:abc则text与s匹配的位置有3和6KMP算法作为一种无回溯的算法，它是高效的，待会儿你将看到它的时间复杂度为O(m+n)，空间复杂度也为O(m+n)而且，它很容易理解，代码也很短定义next:为对应模式串的数组设字符串为s1s2s3...sm,其中s1，s2，s3，...si，...sm均是字符，则next[i]=m，当且仅当满足如
3、下条件：字符串s1s2...smequals字符串s(i-m+1)...si-1si并且s1s2...sms(m+1)unequalss(i-m)s(i-m+1)...si-1si。通俗地讲，next[i]保存了以s[i]为结尾的后缀与模式串前缀的最长匹配数。KMP算法的运行过程我们用两个指针i和j分别表示，A[i-j+1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。如果a[i+1]
4、==b[j+1],i和j各加1，什么时候j==m，就说B是A的子串（B串已经整完了）KMP算法的运行过程如果a[i+1]!=b[j+1],这时候怎么办？i=123456789……A=abababaabab…B=ababacbj=1234567j=5时，a[i+1]!=b[j+1],我们要把j改成比它小的值j‘。改成多少合适呢？KMP算法的运行过程i=123456789……A=abababaabab…B=ababacbj=1234567记住，我们要保持A[i-j+1..i]与B[1..j]完全相等，因而j’是最大的数使a[i-j’+1..i]与B[1.
5、.j’]完全相等.KMP算法的运行过程i=123456789……A=abababaabab…B=ababacbj=1234567显然是求一个最长的以i为末尾的后缀要与B的前缀匹配。由于A[i-j+1..i]与B[1..j]完全相等,故令j’=next[j]即可保证此性质保留KMP算法的运行过程i=123456789……A=abababaabab…B=ababacbj=1234567i=123456789……A=abababaabab…B=ababacbj‘=1234567KMP算法的运行过程需要注意的是i并没有动，改变的只是j的值如果改变j的值后a[
6、i+1]仍不等于b[j+1]的话，继续改变j值直到a[i+1]==b[j+1]或者j=0j=0表示i+1前面无论怎么匹配都不能使a[i+1]==b[j+1],只好让a[i+1]与b[j+1]单独匹配还是上一个例子，再演示一下KMP算法的运行过程i=123456789……A=abababaabab…B=ababacbj=1234567当i=6,j=5时，a[i+1]!=b[j+1],故令j=next[5]=3KMP算法的运行过程i=123456789……A=abababaabab…B=ababacbj=1234567此时i=6,j=3仍不满足a[i+1
7、]==b[j+1]，故继续减小j,使j=next[3]=1KMP算法的运行过程i=123456789……A=abababaabab…B=ababacbj=1234567此时i=6,j=1仍不满足a[i+1]==b[j+1]，故继续减小j,使j=next[1]=0KMP算法的运行过程i=123456789……A=abababaabab…B=ababacbj=1234567终于，A[8]=B[1]，i变为8，j为1KMP算法的运行过程i=123456789……A=abababadbab…B=ababacbj=1234567事实上，有可能j到了0仍然不能满
8、足A[i+1]=B[j+1]（比如A[8]=“d”时）。因此，准确的说法是，当j=0了时，我们直接增加i值但
