34字符串的模式匹配 S551…s52…,sm25m1…Sn1 341朴素模式匹配 PPP…Pm-2Pm1 34.2字符串的特征向量N ■343KMP模式匹配算法 为使模式P与目标S匹配,必须满足 几nP… next 大卿血端张_·权,成 北京大单啦检写@有,赖职 朴素模式匹配 朴素模式匹配代码(简洁) b ababb int Find Pat_2(String S, String P, int startindex)t /g为S的游标,用模板P和S第g位置子串比较 /若失败则继续循环 翼 bb a bb for (int g= startindex; g<= Sstrlen(-Pstrlen O; or(int j=o;((<Pstrlen()&&(S[g+j]==PD) if G== P strlen) return g: return(-1);∥/for结東,或 startindex值过大则匹配失败 b I 大带_息 张写 张所有,赖 MMP算法思想 朴素模式匹配算法代价 5155+15+2 例如, aaaaaaaaaab n1…p2 ■目标S的长度为n,模板P长度为m,m≤n 则有ss152…5=阳P…P(1) 在類藝雞(每m不成功,则 朴素下一越 阳n…P21 如果%1…P2≠几1P2…1 时阁,相潭要知:个字符比校 则立刻可以断定 Po pi 整个算法的最坏时间开销估计为o(m·n) 朴素匹配的)下一趙一定不匹配,可以跳过去 Po p1 p2 next 北底大 张储帖写 真大带健意张写c所有,邮必究 55 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 back next S s0 s1 … si si+1 si+2 … si+m-2 si+m-1 … sn-1 ‖‖ ‖ ‖ ‖ P p0 p1 p2 … pm -2 pm-1 为使模式 P 与目标 S 匹配，必须满足 p0 p1 p2 …pm-1 = si si+1 si+2 … si+m-1 si si+1 si+2 … si+m-2 si+m-1 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 back next 3.4 字符串的模式匹配 „ 3.4.1 朴素模式匹配 „ 3.4.2 字符串的特征向量N „ 3.4.3 KMP模式匹配算法 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 back next 朴素模式匹配 S= P= a b a b a b a b a b a b b a b a b a b b a b a b a b b a b a b a b b Xa b a b a b b X X X a b a b a b bX Xa b a b a b b a b a b a b b 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 back next 朴素模式匹配代码（简洁） int FindPat_2(String S, String P, int startindex) { //g为S的游标，用模板P和S第g位置子串比较， //若失败则继续循环 for (int g= startindex; g <= S.strlen() - P.strlen(); g++) { for (int j=0; ((j<P.strlen()) && (S[g+j]==P[j])) ; j++) ; if (j == P.strlen()) return g; } return(-1); // for结束，或startindex值过大,则匹配失败 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 back next 朴素模式匹配算法代价 例如，aaaaaaaaaab aaaaaab „ 目标S的长度为n，模板P长度为m， m≤n „ 在最坏的情况下，每一次循环都不成功，则 一共要进行比较（n-m+1）次 „ 每一次“相同匹配”需要P和S逐个字符比较 的时间，最坏情况下，共m次 „ 整个算法的最坏时间开销估计为O(m • n) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 back next KMP算法思想 S s0 s1 … si-j-1 si-j si-j+1 si-j+2 … si-2 si-1 si … sn-1 ‖ ‖ ‖ ‖‖ P p0 p1 p2 … pj-2 pj -1 pj 则有 si-j si-j+1 si-j+2 … si-1 = p0 p1 p2 …pj-1 (1) p0 p1 p2 … pj-2 pj -1 如果 p0 p1 …pj-2 ≠ p1 p2 …pj-1 (2) 则立刻可以断定 p0 p1 …pj-2 ≠ si-j+1 si-j+2 … si-1 (朴素匹配的)下一趟一定不匹配，可以跳过去 p0 p1 p2 … pj-2 pj -1 朴素下一趟 × si pj