2014/47 843串的模式匹配算法 int NaiveStrMatch(SeqString T,SeqString P){顺序率上实现 §4.3串的模式匹配算法 inti,j.k; 该算法是将模式串看作是在目标串上向右滑动 int m=P.length,n=T.length; 的模板 for=:1长=n-m:i计+){瓜为合法位移，检查其是否为有效位移 j=0:k=士：心指向摸式，k指向目标 while(j<m&&T.cb一PcbM堂查是香为有效位重 012345 a ca a bc bcaabd k++:j计+：依次检查相应位置是否匹配 位移0 ifG=m)即T.i计m-1=P0m-1,为有效位移 aa b Laa西 returni;返回首次出现的有效位移i,匹配成功 (a)失收右移 (b失敷右移 }//end for return-1:/匹配失败，所有合法位移均不是有效位移 s43串的慎式匹配算法 ⑧43串的模式匹配算法 时间： 2.KMP算法（不带回溯） 最坏情况：对所有合法位移，均要比较到模式的最 下标仍从1算 后一个字符，才能确定位移无效 ■原因分析 即：O(n-m+1)m)o(n*m)∥n>m P右移1位 回湖比较点 最坏情况发生在： 目标串是an-b T:"tm"t H 模式串是am-b∥最后一次成功 P: p…p P1…PiP ·用链串表示时定位运算类似 原因：没有利用部分匹配的结果 若能将模式串右移一段距离，则速度更快 §43模式匹配算法 s43模式匹算法 T:a bb a b a b 若使比较点不回潮（不回），则当 p(T11-1, 失败时有：p=t,pt2,P 即♪的前1个字符与相应T上字符相等： ①若将P右移1位，则，？2，因为 +4pp)时，P中哪个字符应与继续比较7 P邦2，P2=2一P礼，故右移1位后仍失败 因为不动时，必定是将模式右移一段距离，所以不妨设(k) 应与继续比较。 @若将P右移2位，则p,?,因为 Kuth发现，k值仅依赖于P的前个字符的构成，与目标T无关。 P=P3,p共一P,故右移2位后仍失败 采用next1.m]数组，用next[们=k表示当tp时，下 个应与比较的是即 结论：上图比较失败时应直接将P右移3位（即i-1,2,3均为无效 位移)，即直接比较即和，比较点不回潮。 若P中任何字符均无需与1比较，则将p与比较，此时令 next=0。P右移最大 八o:上述观察告诉我们，分折横式本身，就可知道潜在的有效 位移 32014/4/7 3 §4.3 串的模式匹配算法 int NaiveStrMatch ( SeqString T, SeqString P ) { //顺序串上实现 int i, j, k; int m = P.length, n = T.length; for (i = 0; i<=n-m; i++) { //i为合法位移，检查其是否为有效位移 j = 0; k=i; //j指向模式，k指向目标 while(j<m && T.ch[k] == P.ch[j]){ //检查i是否为有效位置 13 k++; j++; //依次检查相应位置是否匹配 } if (j == m) //即T[i..i+m-1]=P[0..m-1]，i为有效位移 return i; //返回首次出现的有效位移i，匹配成功 } //end for return -1; //匹配失败，所有合法位移均不是有效位移 } §4.3 串的模式匹配算法 该算法是将模式串看作是在目标串上向右滑动 的模板 14 §4.3 串的模式匹配算法 时间： 最坏情况：对所有合法位移，均要比较到模式的最 后一个字符，才能确定位移无效 即：O((n-m+1)m)≈O(n*m) // n>>m 最坏情况发生在 15 ： 目标串是 an-1b 模式串是 am-1b // 最后一次成功 用链串表示时定位运算类似 §4.3 串的模式匹配算法 2. KMP算法（不带回溯） 下标仍从1算  原因分析 P右移1位 回溯 比较点 16 T：…ti-j+1…ti … ti-j+1ti-j+2 …ti ti+1 P： p1 ……pj p1……pj-1pj 原因：没有利用部分匹配的结果 若能将模式串右移一段距离，则速度更快 §4.3 模式匹配算法 T: a b b a b a P: a b a 失败时有：p1=t1，p2=t2，p3≠t3 ①若将P右移1位，则p1？t2，因为 p ≠p p =t p ≠t 故右移1位后仍失败 17 p1≠p2， p2=t2 p1≠t2 ，故右移1位后仍失败 ②若将P右移2位，则p1？t3，因为 p1=p3，p3≠t3 p1≠t3，故右移2位后仍失败 结论：上图比较失败时应直接将P右移3位（即i=1，2，3均为无效 位移），即直接比较p1和t4，比较点不回溯。 Note：上述观察告诉我们，分析模式本身，就可知道潜在的有效 位移 §4.3 模式匹配算法 若使比较点不回溯（i不回溯），则当 ti ≠pj （T[i-j+1..i-1]=P[1..j-1]， 即P的前j-1个字符与相应T上字符相等： ti-j+1…ti-1=p1…pj-1）时，P中哪个字符应与ti 继续比较？ 因为i不动时，必定是将模式右移一段距离，所以不妨设pk（k<j） 应与 继续比较 18 ti 。 Knuth发现，k值仅依赖于P的前j个字符的构成，与目标T无关。 采 用 next[1..m] 数组，用 next[j]=k 表示当 ti ≠pj 时，下一 个应与ti 比较的是pk 若P中任何字符均无需与ti比较，则将p1与ti+1比较，此时令 next[j]=0。P右移最大