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】〔1<=s[0]曼<=0]) (S[=叫){++1+}∥继续比较后继字符 =-j+2;j=1;}∥指针后退重新开始匹配 (>T[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