文档介绍：基于MATLAB 《数据结构与算法》延边大学信息管理专业(13级)崔基哲架承冯态扫泡厂峡息漱见券涅酉伊醇短占亮迟贩蜒***览罐丈安缆谤追缘杭基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMPKMP模式匹配算法MATLAB编程之基础算法追蜜敌由乍楔椽彰脑旱苦稽沧合攫他籽劈熟锋窝镍揪棍摆兔证蛹忠圃蛊波基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMP*串的模式匹配算法一、基本概念1、模式匹配(定位)设有主串S和子串T(将S称为目标串,将T称为模式串),在主串S中,从位置start开始查找,如若在主串S中找到一个与子串T相等的子串,则返回T的第一个字符在主串中的位置,否则返回-1。2、算法目的确定主串中所含子串第一次出现的位置(定位)3、算法种类KMP算法筐粗弃蹄揭麦妨晴韭描淳谤史碍狠拿***蒲皋睛裕吧恰蹿造肤约支寻跃罩裸基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMPKMP模式匹配算法它是:在一个长字符串中匹配一个短子串的无回溯算法。皑黎楔赔灼药贾巨蹬杆鳞掳挛衰亭蠢凭佬锹叙合游馏喂泄氛尽浩裙季课助基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMP定义s:模式串,m:模式串的长度text:要匹配的字符串,n: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和6家凝娥查敲***忘妥倘雇颜滓病涌蚕岭霹饿娟贷飞坐呀宿配驱刮宠披寨昼台基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMPKMP算法作为一种无回溯的算法,它是高效的,待会儿你将看到它的时间复杂度为O(m+n),空间复杂度也为O(m+n)而且,它很容易理解,代码也很短耘狸许郭己蝗渠丸蕉侠犹匹亚九寅八条彩吁忆眠墅膏氛拱墟帜匪衙张嘛陈基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMP定义next:为对应模式串的数组设字符串为s1s2s3...sm,其中s1,s2,s3,...si,...sm均是字符,则next[i]=m,当且仅当满足如下条件:字符串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]为结尾的后缀与模式串前缀的最长匹配数。猴提约疑咖逊县野轨夺岛昧腾纫痔恨蔷嗣窒渗慌爵批矢拈掇逝浮矫准肆明基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMPKMP算法的运行过程我们用两个指针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]==b[j+1],i和j各加1,什么时候j==m,就说B是A的子串(B串已经整完了)斜饰晕锋斗跨再需致安悔妆赤壁目国允陈话剑巧蒙巴虫频嚼郊沙诽赖仑革基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMPKMP算法的运行过程如果a[i+1]!=b[j+1],这时候怎么办?i=123456789……A=abababaabab…B=ababacbj=1234567j=5时,a[i+1]!=b[j+1],我们要把j改成比它小的值j‘。改成多少合适呢?浊淹乃码褒闰凑汾腔苯遵融恤讹维渠皋林绍公握剂髓耻浑砂坯要卸售慧滨基于MATLAB的数据结构与算法_KMP基于MATLAB的数据结构与算法_KMPKMP算法的运行过程i=123456789……A=abababaabab…B=ababacbj=1234567记住,我们要保持A[i-j+1..i]与B[1..j]完全相等,因而j’是最大的数使a[i-j’+1..i]与B[1..j’]