4.3串的模式匹配算法 27
28 串的模式西配 子串的定位操作又称为模式匹配(Pattern Matching) 或串匹配(String Matching),其中子串T被称为模 式串。 此操作的应用在非常广泛。例如，在文本编辑程序 中，我们经常要查找某一特定单词在文本中出现的 位置。显然，解此问题的有效算法能极大地提高文 本编辑程序的响应性能
13 29 林素的模式巫配算法 第1趟S a bb a b a T a b a 穷举的模式匹配方法 【基本思想（同算法41）】 从主串S的第pos个字待 第2趟S a bb a b a 起和模式T的第一个字 T a 符比较，若相等，则继 续逐个比较后继字符， 第3趟S a bb 否则从主串的下一个字 ab a T 符起重新和模式T的字 符比较。依此类推，直 到找到匹配成功，或匹 第4趟S a bb a b 配失败。 T a b 返回i=4
30 林素的模式区配算法(3) it Index(SString S,SString T,int pos) ∥返回子串T在主串$中第3个字符之后的位量。若不存在，则函数值为0。 ∥其中，T非空，1≤pog≤StrLengt)(s)。 i=pas;j=1; h(i<=s[0]&&方<=[0]){ 证(s[]=[]){++1: ++:}∥继续比较后继字符 1w{1=1-j+2: j=1;} ∥指针后退重新开始匹配 f(j>[0]) t i-[0]: alse ratura 0; k∥Index i-j+1 i-j+2 i-1 1 2
31 朴素的模式匹配算法(4) 算法简单，易于理解，但效率不高，主要原因是执 行中有回溯，一旦比较不等，就将指针右移一个字 符，并从模式串的开头重新开始比较。 ·在最坏的情况下，每趟比较都在最后出现不等，最多比 较n-m+1趟，总比较次数为m(n-m+1),由于在一般 情况下m<<n,所以算法运行时间为O(m*n)。 【例】 主串： 000000000000000000000000000000000000000000001 模式串： 00000001