武汉理工大学-信息工程学院-数据结构-ppt-课件ch04-2-串2-模式匹配

第4章串数据结构讲义信息工程学院魏洪涛Email:[e-mail]这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。子串（模式串）的定位操作通常称为串的模式匹配。4.3串的模式匹配算法初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若返回子串T在主串S中第pos个字符之后的位置。如果不存在，则返回0.首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)例如：S=“Thisisabook.”T=“is”pos=1BF算法设计思想：•将主串的第pos个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。BF算法（又称古典或经典的、朴素的、穷举的）KMP算法（特点：速度快）算法种类：•直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。•否则，匹配失败，返回值0.S=‘ababcabcacbab’T=‘abcac’pos=5ababcabcacbababci=3,j=3ababcabcacbabai=2,j=1ababcabcacbababcaci=7,j=5ababcabcacbabai=4,j=1ababcabcacbabai=5,j=1ababcabcacbababcaci=11,j=6T=abcacBF算法的实现串匹配算法过程演示ch4_string_match.c讨论：若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为：(n-m+1)*m＝O(n*m)最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次.但一般情况下BF算法的时间复杂度为O(n+m)00000000010001000000000100010000000001000100000000010001000000000100010000000001000100000000010001000000000100010000000001000100000000010001000000000100010000000001000100000000010001000000000100014.3.2模式匹配的一种改进算法KMP算法的基本思想：每一趟匹配完成后，利用上一趟匹配的结果，将模式向右滑动尽可能远的一段距离。其方法是：不回溯指针i，找出主串中第i个字符应和模式串的第几个字符比较。此方法有两个问题要解决：1，此种方法会不会漏掉可能的匹配？2，主串中第i个字符应和模式串的第几个字符比较。设主串为's1s2…sn'，模式串为'p1p2…pm'假设上一趟比较中最后主串的第i个字符和模式串的第j个字符不相等（前j-1个字符均相等）即有：'p1p2…pj-1'='si-j+1si-j+2…si-1's1s2…si-j+1si-j+2…si-1si……snp1p2…pj-1pj…pm若在主串的第i-j+2到第i位之间有一个匹配如：s1s2…si-j+1…si-k+1…si-1si……snp1p2…pk-1pk…pm则此时Si应和pk，即模式串中的第k个字符比较.acabaabaabcacaabcabaabci=8,j=6即主串的第i个字符前有k-1个字符和模式串的前k-1个字符相等：'p1p2…pk-1'='si-k+1si-k+2…si-1'而根据上一趟比较有'p1p2…pj-1'='si-j+1si-j+2…si-1'因此有：'p1p2…pk-1‘='pj-k+1pj-k+2…pj-1'acabaabaabcacaabcabaabci=8,j=6abaabci=8,j=3abaabck=3,j=6令next[j]=k，则有0当j=1时next[j]=max{k|1kj且'p1p2…pk-1'='pj-k+1pj-k+2…pj-1'}1其它情况显然next[j]只与模式串有关，与主串无关j12345678模式串next[j]abaabcac01122312j1234567891011模式串next[j]aabbaabbaab01211234567i=2acabaabaabcacaabcabj=2next[2]=1i=2acabaabaabcacaabcaj=1next[1]=0i=3-i=8acabaabaabcacaabcabaabcj=6next[6]=3i=8-----i=14acabaabaabcacaabcabaabcacj=9j12345678模式串next[j]abaabcac01122312intIndex_KMP(SStringS,SStringT,intpos){//利用模式串T的next函数求T在主串S中第pos个字符之后的位//置的KMP算法，其中T非空，1≤pos≤StrLength(S)i=pos;j=1;while(i=S[0]&&j=T[0]){if(j==0||S[i]==T[j]){++i;++j;}elsej=next[j];}if(jT[0])returni-T[0];elsereturn0;}算法4.6算法时间复杂度O(n+m)第4章小结串s=“a1a2……..an”定长顺序存储结构块链存储结构堆存储结构逻辑结构存储结构操作(或运算)模式匹配算法若干函数的实现模式匹配即子串定位运算，即如何实现Index(S,T,pos)函数BF算法———古典KMP算法——快速（用next[j]或nextval[j])本章结束作业：已知主串S=“ADBADABBAABADABBADADA”模式串T=“ADABBADADA”求next函数值，并给出其KMP算法匹配的全过程