简单的模式匹配算法 a int StrMatch(SString S, SString P)t whl(i<=S[0]&&j<P[O]){ if(S[=P[j){计+;j+;} else i=i-j+2;j=1) ifJ> plod return 1-P[OJ: return o 2021/22 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 简单的模式匹配算法 ◼ int StrMatch(SString S, SString P)｛ ◼ i = 1； j = 1； ◼ while(i <= S[0] && j <= P[0])｛ ◼ if (S[i] == P[j])｛i++; j++;｝ ◼ else {i = i – j + 2； j = 1} ◼ ｝ ◼ if(j > P[0]) return i – P[0]； ◼ return 0; ◼ ｝
简单的模式匹配算法的评估 ■在回朔深度不大的情况下,模式匹配算 法的时间复杂度为Om+n) ■在最坏情况下的时间复杂度为O(n*m) 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 简单的模式匹配算法的评估 ◼ 在回朔深度不大的情况下，模式匹配算 法的时间复杂度为O(m+n) ◼ 在最坏情况下的时间复杂度为O(n*m)
KMP算法 ■KMP算法是D. Knuth与VPra6J. Morris同时 发现的,故称为 Knuth morris pratt算法, ■其思想是:每当匹配过程中出现字符不等时, 不是简单地从正文的下一个字符(即+1)开始重 新比较,而是利用已经得到的“部分匹配”的 结果将模式串向右“滑动”尽可能远的一段距 离后,再进行比较。 KMP算法的时间复杂度为O(n+m) 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 KMP算法 ◼ KMP算法是D. Knuth与V. Pratt和J. Morris同时 发现的，故称为Knuth_Morris_Pratt算法。 ◼ 其思想是：每当匹配过程中出现字符不等时， 不是简单地从正文的下一个字符(即i+1)开始重 新比较，而是利用已经得到的“部分匹配”的 结果将模式串向右“滑动”尽可能远的一段距 离后，再进行比较。 ◼ KMP算法的时间复杂度为O(n+m)
能向右滑动多远? 于是得到这样的结果: Pr..Pk-1pi P k+1··i-1 而由前次的比较应有:s1k+1…s1=p1k+1…,p1=1° p p p1|…P1 m 显然应有:sk1s1=p1,p 2021/221 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 9 能向右滑动多远？ p1 … pk … pj … pm s1 …… si …… sn 当si pj，就将模式向右移动。假设pk和si相比较： s1 …… si …… sn p1 … pk … pj … pm 显然应有：si–k+1…si–1 = p1…pk–1。 s … p1 … 而由前次的比较应有：si–k+1…si–1 = pj–k+1 …pj–1。 于是得到这样的结果： p1…pk–1 = pj–k+1 …pj–1
滑动的距离只取决于模式 ■模式滑动距离只取决于模式本身,与正文无关。 ■设函数next为当模式中第j个字符与正文中相 应字符“失配”时,在模式中需重新和正文中 该字符进行比较的字符的位置 0当j=1时 a next[]= max (k|1<k<j Ep.Pk-1=pik+lPi) 1当不存在相应的k时 2021/221 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 10 滑动的距离只取决于模式 ◼ 模式滑动距离只取决于模式本身，与正文无关。 ◼ 设函数next[j]为当模式中第j个字符与正文中相 应字符“失配”时，在模式中需重新和正文中 该字符进行比较的字符的位置。 0 当j=1时 ◼ next[j] = max {k |1<k<j且p1…pk–1= pj–k+1…pj–1} 1 当不存在相应的k时