数据结构4串市公开课一等奖省赛课获奖课件

数据结构

4

串1数据结构4串第1页开始学习本章前要知道：从数据结构角度看，串也属于线性结构，含有线性结构共同特征；学习本章时，要注意到串所含有线性结构共性，更要掌握其个性；串特殊性主要是：串元素是字符。2数据结构4串第2页主要内容串模式匹配简单算法KMP算法3数据结构4串第3页模式匹配(在主串S中定位子串T（模式串）)回想一下串匹配定义：index(S,T)初始条件：串S和T存在操作结果：若主串S中存在和串T值相同子串，返回它在主串S首次出现位置；不然返回0比如主串S=子串T=CD则index(S,T)，返回子串T在S中，第一次出现位置3串模式匹配4数据结构4串第4页串模式匹配

Brute-Force算法基本思想：从目标串s第一个字符起和模式串t第一个字符进行比较若相等，则继续逐一比较后续字符，不然从串s第二个字符起再重新和串t进行比较。依这类推，直至串t中每个字符依次和串s一个连续字符序列相等，则称模式匹配成功，此时串t第一个字符在串s中位置就是t在s中位置，不然模式匹配不成功。5数据结构4串第5页Brute-Force算法C语言描述以下：intIndex(strings,stringt){inti=0,j=0;//i,j分别指向串s、t第1个字符while((i<s.curlen)&&(j<t.curlen))if(s.str[i]==t.str[j]){++i;++j;}

//当前字符匹配，i,j递增else{i=i-j+1;j=0;}

//匹配失败，j返回子串首，i回退到下次匹配起点if(j>=t.curlen)return(i-t.curlen);//匹配成功，返回串t在串s中起始位置elsereturn0;//匹配失败返回0}6数据结构4串第6页ij0123456789101112ababcabcacbababcac01234while((i<s.curlen)&&(j<t.curlen))if(s.str[i]==t.str[j])//当前字符匹配，i,j递增{++i;++j;}else//匹配失败，j返回子串首，i回退到下次匹配起点{i=i-j+1;j=0;}7数据结构4串第7页串模式匹配:简单算法算法分析最好情况主串S和模式T中每个字符都只访问了一次复杂度=O(n+m)bbbbbabcacijabcac8数据结构4串第8页最差情况主串S中每个字符，分别和模式T中每个字符匹配一次复杂度=O(n*m)串模式匹配:简单算法bbbbbaijbbba9数据结构4串第9页由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出了一个改进算法，消除了Brute-Force算法中串s指针回溯，完成串模式匹配。基本思想：在简单算法基础上，i不要回退，模式串尽可能多往右移时间复杂度为O(s.curlen+t.curlen)，这就是Knuth-Morris-Pratt算法，简称KMP算法。串模式匹配:KMP算法10数据结构4串第10页利用已经部分匹配结果信息，尽可能让i不要回溯，加紧模式串滑动速度。例：S=‘ababcabcacbab’T=‘abcac’ikabaabcS=‘ababcabcacbab’T=‘abcac’ikS=‘ababcabcacbab’T=‘abcac’ik需要讨论两个问题：①怎样由当前部分匹配结果确定模式串向右滑动新比较起点k？②模式串应该向右滑多远才是高效率?11数据结构4串第11页请抓住部分匹配时两个特征：T=‘abcac’(1)S=‘ababcabcacbab’ik设S第i字符当前打算与T第k字符开始比较k是追求新起点则Tk-1~0=S前i-1~i-k位匹配“T0…Tk-1”(2)刚才必定是在Si处和T第j字符处失配S=‘ababcabcacbab’T=‘abcac’ikj则Tj-1~j-k位=S前i-1~i-k位匹配“Tj-k…Tj-1”截取一段，但k有限制，0<k<j两式联立可得：“T0…Tk-1”=“Tj-k…Tj-1”注意：j为当前已知失配位置，我们目标是计算新起点k。式中仅剩一个未知数k，理论上已可解！奇妙结果：k仅与模式串T相关！12数据结构4串第12页依据模式串T规律：“T0…Tk-1”=“Tj-k…Tj-1”由当前失配位置j(已知)，归纳计算新起点k表示式。新起点k怎么求？next[j]=0当j=1时max{

k|1<k<j且‘T0…Tk-1’=‘Tj-k…Tj-1’

}1其它情况注意：(1)k值仅取决于模式串本身而与相匹配主串无关。(2)k值为模式串从头向后及从j向前两部分最大相同子串长度。(3)这里两部分子串能够有部分重合字符，但不能够全部重合。令k=

next[j]（k与j显然含有函数关系），则取T首与Tj处最大相同子串13数据结构4串第13页next[j]=0当j=1时max{k|1<k<j且‘T0…Tk-1’=‘Tj-k…Tj-1’}1其它情况next[j]函数表示模式T中最大相同前缀子串和后缀子串（真子串）长度。可见，模式中相同部分越多，则next[j]函数越大，它既表示模式T字符之间相关度越高，也表示j位置以前与主串部分匹配字符数越多。即：next[j]越大，模式串向右滑动得越远，与主串进行比较次数越少，时间复杂度就越低（时间效率）。14数据结构4串第14页i、j分别为指示s(目标串)和t(模式串)指针，初值均为1。若si=tj，则i和j分别增1；不然，i不变，j退回至j=next[j]位置(即串s不动，模式串t向右移动到si与tnext[j]对齐)；比较si和tj。若相等则指针各增1；不然j再退回到下一个j=next[j]位置(即模式串继续向右移动)，再比较si和tj

。KMP算法基本思想依次类推，直到以下两种情况之一：1)j退回到某个j=next[j]时有si=tj，则指针各增1，继续匹配；2)j退回至j=0，此时令指针各增1，即下一次比较si+1和t0。15数据结构4串第15页串模式匹配：KMP算法模式串next函数意义：j之前子串中，左起一段=右起一段，最长能够到k1...k-1kj-k+1...j-1j16数据结构4串第16页串模式匹配：KMP算法比如：0j12345678模式串abaabcacnext[j]112231217数据结构4串第17页串模式匹配：KMP算法j123456子串abcabdnext[j]01112312345678910abcabcabdcjiabcabd123456此次匹配失败让j=next[j]=318数据结构4串第18页KMP算法了解S[i]!=T[j]，说明i之前字符都匹配则S[4..5]=T[4..5]next[j]=3，说明T[1..2]=T[4..5]所以T[1..2]=S[4..5]ji12345678910abcabcabdcabcabd123456ST19数据结构4串第19页KMP算法疑问1：子串T会不会向前走得太多了？假设只向前走一个字节可不可能呢？假如能够话，则T[1..4]=S[2..5]而刚才已知T[1..5]=S[1..5]则S[1..4]=S[2..5]也就是T[1..4]=T[2..5]那么next[6]=5，和已知next[6]=3矛盾！12345678910abcabcabdcabcabd123456ST20数据结构4串第20页KMP算法同理：向前走2个字节也不可能假如能够话，则T[1..3]=S[3..5]而刚才已知T[1..5]=S[1..5]则S[1..3]=S[3..5]也就是T[1..3]=T[3..5]那么next[6]=4，和已知next[6]=3矛盾！12345678910abcabcabdcabcabd123456STji21数据结构4串第21页KMP算法ji12345678910abcabcabdcabcabd123456ST疑问2：可不能够多向前走一些呢？主串往往很长，不可能全部分析所以只能经过分析子串来分析主串而当前最多知道T[1..2]匹配S[4..5]并不能确保T[1..]匹配S[5..]22数据结构4串第22页串模式匹配：KMP算法next函数计算一个递归过程：已知next[1]=0若next[j]=k说明有‘p1...pk-1’=‘pj-k+1...pj-1’若pk=pj，则next[j+1]=k+1若pk!=pj，令k’=next[k]若pk’=pj，则next[j+1]=k’+1若pk’!=pj，则尝试next[k’]...23数据结构4串第23页串模式匹配：KMP算法分析首先next[1]=0假设已知next[j]=knext[j+1]=?12345678910111213子串abcabdabcabcanext0jk6?24数据结构4串第24页串模式匹配：KMP算法分析若T[k]=T[j]则next[j+1]=k+112345678910111213子串abcabdabcabdanext06jk725数据结构4串第25页串模式匹配：KMP算法分析若T[k]!=T[j]令k’=next[k]若T[k’]=T[j]，则next[j+1]=k’+112345678910111213子串abcabdabcabcanext06jk4k’26数据结构4串第26页串模式匹配：KMP算法为何令k’=next[k]？next[12]=6，说明T[1..5]=T[7..11]k’=next[k]=3，说明T[1..2]=T[4..5]则T[1..2]=T[10..11]若又有T[k’]=T[j]，则next[j+1]=k’+112345678910111213子串abcabdabcabcanext06jk4k’27数据结构4串第27页串模式匹配：KMP算法匹配函数intIndex_KMP(SStringS,SStringT,intpos){ i=pos; j=1;

while(i<=S.curlen&&j<=T.curlen){if(j==0||S[i]==T[j]){i++;j++;}

else j=next[j];

//模式串右移

}

if(j>T.curlen)returni-T.curlen;

//匹配成功

else

return0;

//失败

}28数据结构4串第28页串模式匹配：KMP算法计算next函数voidget_next(SSTringT,intnext[]){ j=1;next[1]=0; k=0;

while(j<T.curlen) { if(k==0||T[j]==T[k]){j++;k++;next[j]=k;}

else k=next[k]; }//while}29数据结构4串第29页KMP算法next函数不足12345子串aaaabnext0123412345678910aaaacaaaabjiaaaab12345ST30数据结构4串第30页12345678910aaaacaaaabjiaaaab12345STKMP算法next函数不足12345子串aaaabnext01234经过对子串分析可知T[3]=T[4]假如现在T[4]和S[5]不匹配，还需要再尝试T[3]和S[5]么？那就尝试T[3]下一个T[2]结果T[2]=T[3]所以尝试T[2]下一个T[1]结果T[1]=T[2]T[1]下一个next[1]=0所以j=1;i++;31数据结构4串第31页串模式匹配：KMP算法next函数改进设k=next[j]，其含义是当T[j]和S[i]不匹配时，尝试T