串的模式匹配ppt课件.ppt

《串的模式匹配ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、这是串的一种重要操作，很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。4.3串的模式匹配算法初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)操作结果：若主串S中存在和串T值相同的子串返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。intIndex(StringS,StringT,intpos){//T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0if(pos

2、>0){n=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;elsereturni;}//while}//ifreturn0;//S中不存在与T相等的子串}//Index下面讨论以定长顺序结构表示串时的几种算法。一、简单算法三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法二、首尾匹配算法S串T串T串iposn-m+1S串T串T串ijj>mijijiji>njT

3、串一、简单算法intIndex(SStringS,SStringT,intpos){//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。//其中，T非空，1≤pos≤StrLength(S)。i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i;++j;}//继续比较后继字符else{i=i-j+2;j=1;}//指针后退重新开始匹配}if(j>T[0])returni-T[0];elsereturn0;}//Index先比较模式串的第一个字符，再比较模式串的最后

4、一个字符，最后比较模式串中从第二个到第n-1个字符。二、首尾匹配算法首尾匹配算法假设开始比较的位置为posi=(pos---S[0])j(1—T[0])从pos位置开始进行字符串的匹配比较每次一般j=1S[i]==T[1]再比较T[T[0]]==S[I+T[0]-1]首尾均相等的话拿j（2—T[0]-1）的字符逐一和S[i+j-1]intIndex_FL(SStringS,SStringT,intpos){sLength=S[0];tLength=T[0];i=pos;patStartChar=T[1];patEndChar=T[tLe

5、ngth];while(i<=sLength–tLength+1){if(S[i]!=patStartChar)++i;//重新查找匹配起始点elseif(S[i+tLength-1]!=patEndChar)++i;//模式串的“尾字符”不匹配else{}}return0;}检查中间字符的匹配情况k=1;j=2;while(j

6、配过程中出现字符比较不相等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法通过已经走过的路，可以求出下一个j开始的位置，j=1/j越大越好模式串“abaabcac”S13ababcabcacbab012345678910111213T5abcac012345ijijijiiiiiiijjji当主串中第i个字符与模式中的第j个字符失配时，主串中的第i个字符应与模式中的哪一个字符再比较算法思想主串：s

7、:‘s(1)s(2)s(3)……s(n)’;模式串：p:‘p(1)p(2)p(3)…..p(m)’;假设主串第i个字符与模式串的第j(j<=m)个字符‘失配’后，主串第i个字符与模式串的第k(k

8、

9、(相配)

10、

11、≠(失配)　　匹配串：P(1)…….p(j-1)p(j)算法思想由此，我们得到关系式‘p(1)p(2)p(3)…..p(j-1)’=’s(i-j+1)……s(i-1)’由于s(i)≠p(j)，接下

12、来s(i)将与p(k)继续比较，则模式串中的前(k-1)个字符的子串必须满足下列关系式，并且不可能存在k’>k满足下列关系式：(k