4.3串的模式匹配算法
28 串的模式匹配 子串的定位操作又称为模式匹配(Pattern Matching) 或串匹配(String Matching),其中子串T被称为模 式串。 此操作的应用在非常广泛。例如在文本编辑程序 中,我们经常要查找某一特定单词在文本中出现的 位置。显然,解此问题的有效算法能极大地提高文 本编辑程序的响应性能
i=1i=2i=3 29 第1趟S 朴素的模式匹配算法 a bb aba T a b 穷举的模式匹配方法 【基本思想(同算法41)】 从主串S的第pos个字神 第2趟S· a bb a b a起和模式T的第一个字 T b a 符比较,若相等,则继 i=3 续逐个比较后继字符, 第3趟 s a bb ab 否则从主串的下一个字 b 符起重新和模式的字 符比较。依此类推,直 4=7到找到匹配成功,或匹 第4趟 s abb aba*配失败 T a b a 返回i=4 j=1j=23j=4
朴素的模式匹配算法(3) int Index(sstring S, SString T, int pos) ∥返回子串T在主串8中第p个字符之后的位量。若不存在,则函数值为0。 ∥其中,T非空,1≤pos≤ strEngth($)。 os; Mh】〔1T[0])i-0]; ds ntum O: t∥ Index ij+1i+2……i1i S 12…j1j T
朴素的模式匹配算法(4) ■算法简单,易于理解,但效率不高,主要原因是执 行中有回溯,一旦比较不等,就将指针右移一个字 符,并从模式串的开头重新开始比较。 ·在最坏的情况下,每趟比较都在最后出现不等,最多比 较n-m+1趟,总比较次数为m*(n-m+1),由于在一般 情况下m<<n,所以算法运行时间为Om*n) 【例】 主串: 00000000000000000000007 模式串: “00000001
改进的模式匹配算法——KMP算法 i=1i=2i=3 D.E. Knuth与 第1趟S·ab.baba V.R. Pratt/fu Ta b a J.H. Morris同时发现。 的,故简称为KMP算 法 第2趟 s ab b a b a 不回湖! T b a i=4i=5i=6i=7 第3趟 s abb ba T b a 返回i=4
改进的模式匹配算法——KMP(2) i=1i=2i=3 第1趟 s. ab bca bcacba b T a b c a c 每当出现失配时,i指针和回 溯,而是利用已经得到的“部分 21213匹配”结果将模式向右“滑动”尽 可能远的一段距离后,继续比较 第2趟Saba, b c abc, a cb a b j=1j=2 j13j=4j =7i=8i=9i=10i=11 第3趟 s a b ab cabc, a cb ab ab 返回=6 2j=3j=4j=5j=6
失配时模式向右滑行的距离 假设主串SS2…s,模式串PP2Pmn’当主串 中第个字符与模式串中第j个字符“失配”时,主串中 第i个字符应与模式串中第k个字符再比较 S H)+1|S+2……Sk18+2…8H8 ‖x T P1|P2 p p j-k+1Pi-k+ 、、 滑动后 T PI P2 Pk-1 Pk 【实质】k-1为pP2 的最大相同真前缀稹真 后缀的长度!
35 模式串的next菡数定义 ■若令next-k,则next表明当模式串中第个字符 与主串中第个字符“失配”时,在模式串中需重新和 主串中该字符进行比较的字符的位置 Q 0,当=时←此时,指针和应当同时增加1 JnextLil=Maxk 1<<jHPrPk-1Pi-k+"Pi-13, 当此集合不空时 1,其它情况 next函数有时也称为失效函数 ·next函数值与道值无关! 【例1】 【例2】 模式串 a b ca 模式串(ab) a cabc next[] 0 next] 0
36 KMP算法 int Inder_MP(sString S, sString T, int pos)1 ∥利用糗式申的ne函数求丌在主申S中第poa个字符之后的位置的 ∥p算法。其中,T非空,1≤pos≤ strEngth(S)。 j=1; Mh1·(i型[0])rts1實0]; ∥匹配成功 alae retum 0t ∥ndex.8 int Index(sstring S, sString T, int poa)I ∥返国子串T在主串8中第pa个字符之后的位量。若不存在则函数值为0。 ∥其中,T非空,1≤po≤ strEngth($) Mh】(r[0]) TO nturn 0 ∥ Index
