201447 S4.3模式匹配算法 §43模式匹配算法 ■算法若已知next1.m则匹配算法如下 P的右移位数为：j-next[j们 int KMPMatch(char Tll,char Pll){/TIo和P叫O分别表示长度 少右移 n-TI01;m-P0;/长度 jPl:开始rp j1… j+1…tk+1…t while(<=n&&j-m） if il-PljD) p1…pi… Pi…pk…pir ++:继蝶比较下一位 }else{M≠p k-nextijl; 右移-k+1-(-j十1)广jk if (k>0) jPk;比较t和ptrp else{ j-l;it+; }/比较和即t+P 】//endif.endwhile S43摸式匹配算法 S43模式匹配算法 算法 next数组的性质 if>m)匹配成功 ①整数数组：0飞next[jl<j,即0sk<j return i-m;/注意成功时，和j均多加了1 ⑧当时， 若ext-k>0,则比较t和p,此时有 Tk+1-1-P叫1k-11/长度为k-1 else Tij+1i-1P叫1j-11失败前部分匹配，长度为j-1 return0:/匹配失败 Pjk+lj-i-PILk-Ip…pL"-p-k+p” 3 当邦，时，k的值应等于串P1小中前后缀相等的子串的长度 加1 ◆时间：循环主要取决于只增不减，因为>m,所 以时间为O(n P1…p-k+1…P-iPj- ∥前j-1个字符相等 P右移jk位： P1…pk-iPk ]/前k-1个字符相等 22 843模式匹配算法 §4.3模式匹配算法 ③当满足性质2的k有多个（即前后绿相等的子串有多 真子串不包括自身，但包括空串 个)时，应取最大的k值。 原因：k最大，模式P右移-k最少，不丢失任何匹配 真子串：”aa”,“a”,“” 机会。 长度：210 例：j1234 Taaa是bbbb P右移1位，匹配成功 k:321 Pa aa b P右移2位、3位均失败 在P13引中，k=3最大，j-k=1位右移最少，k=2, k=1时失去匹配机会 即P13引中，前后绿相等的最大真子串为 P12=P231,长度+1-3-k2014/4/7 4 §4.3 模式匹配算法 P的右移位数为：j-next[j] …ti-j+1 …ti … ti-j+1…ti-k+1……ti p1……pj… p1……pk…pj … j-k 右移j-k ？ 19 p1……pj… p1……pk…pj … 右移i-k+1-(i-j+1)=j-k  算法 若已知next[1…m],则匹配算法如下： int KMPMatch ( char T[] ,char P[] ) { //T[0]和P[0]分别表示长度 n=T[0] ; m=P[0] ; //长度 i=j=1; //开始 t1~p1 while (i<=n && j<=m) if (T[i]==P[j]) { i j //继续比较下 位 §4.3 模式匹配算法 20 i++; j++; //继续比较下一位 } else { //ti ≠ pj k=next[j]; if (k>0) j=k ; //比较ti 和pk: ti ~pk else { j=1; i++; } //比较ti+1和p1:ti+1~p1 } //endif，endwhile  算法 if (j>m) //匹配成功 return i-m; //注意成功时，i和j均多加了1 else return 0; //匹配失败 §4.3 模式匹配算法 21 }  时间：循环主要取决于i只增不减，因为n>>m，所 以时间为O(n)  next数组的性质 ① 整数数组：0≤next[j]<j，即0 ≤k<j ② 当ti ≠pj 时，若next[j]=k>0，则比较ti 和pk，此时有: T[ i-k+1..i-1 ]=P[ 1..k-1 ] //长度为k-1 T[ i-j+1..i-1 ] =P[ 1..j-1 ] //失败前部分匹配，长度为j-1 P[ j-k+1..j-1 ]=P[1..k-1] // “p1…pk-1”=“pj-k+1…pj-1” §4.3 模式匹配算法 22 当ti ≠pj 时，k的值应等于串P[1…j-1]中前后缀相等的子串的长度 加1 T：…ti-j+1… ti-k+1 … ti-1 ti … p1……pj-k+1…pj-1pj … // 前j-1个字符相等 P右移j-k位： p1……pk-1pk… // 前k-1个字符相等 ？ ③ 当满足性质2的k有多个（即前后缀相等的子串有多 个）时，应取最大的k值。 原因：k最大，模式P右移j-k最少，不丢失任何匹配 机会。 例: j 1 2 3 4 Ta a a a b b bb §4.3 模式匹配算法 P右移1位，匹配成功 23 T a a a a b b b b P a a a b 在P[1..3]中，k=3最大，j-k=1位右移最少，k=2， k=1时失去匹配机会 即P[1..3]中，前后缀相等的最大真子串为 P[1..2]=P[2..3]，长度+1=3=k P右移1位，匹配成功 P右移2位、3位均失败 §4.3 模式匹配算法 真子串不包括自身，但包括空串 真子串：”aa” , “a” , “” 长度： 2 1 0 k ： 3 2 1 24