字符串匹配算法：穷举、KMP、BM.ppt

算法分析 上述计算d的算法的运行时间为Θ(m)，BM算法的最坏情况在每轮匹配比较了m个字符后才失败的情况下发生，运行时间为Θ(mn)。 第七章　　结束 字符串 (String) 字符串是n ( ? 0 ) 个字符的有限序列，记作 S : “c0c1c2…cn-1” 其中，S是串名字 “c0c1c2…cn-1”是串值 ci是串中字符 n是串的长度。 如：“Welcome to Shanghai !!!” 在计算机非数值计算应用中，经常遇到字符序列的处理。如，文字编辑、情报检索、自然语言翻译、事务处理、图象处理等应用中经常遇到的那样。在计算机中，一个字符集上的每个字符用定长的代码表示，所有可能的各种字符都可以对应一个确定的代码。一个特定的字符序列称为字符串，简称为串。有两种方法能比较方便地表示一个字符串。一是人为地约定一个特殊的代码为字符序列的结束符，每个字符串最后都有这个结束符。二是，为每个字符序列另引入一个整数，让该整数指出该字符串的字符个数。本书采用第一种表示字符串的方法 模式匹配是串的基本运算之一。 有两个字符串T和Ｓ，字符串T称为正文，字符串S称为模式，要求找出模式S在正文T中的首次出现的位置。一旦模式S在正文T中找到，就说发生一次匹配。有些应用可能会要求找出所有的匹配位置。 串的模式匹配 定义 在串中寻找子串（第一个字符）在串中的位置 词汇 在模式匹配中，子串称为模式，串称为目标。 示例 目标 T : “Beijing” 模式 P : “jin” 匹配结果 = 3 记正文T的字符个数为n，令 T= t0t1t2…tn-1， 记模式S的字符个数为m，令 S= s0s1s2…sm-1。 若正文中自位置k开始有一次匹配，则有 sj = tk+j，0 = j m。 并且对所有pk，没有对所有的0=jm，m个等式 sj = tp+j 全都成立。 7.1 简单匹配 第1趟 T a b b a b a 穷举的模式 P a b a 匹配过程 第2趟 T a b b a b a P a b a 第3趟 T a b b a b a P a b a 第4趟 T a b b a b a P a b a ? char *stringSearch(char *t, char *p) { int n = strlen(t), m = strlen(p), i, j; for(j = 0; j = n - m; j++) { /* 从t[j]开始的子串与字符串p比较 */ for(i = 0; i m t[j+i] == p[i]; i++); if (i == m) return t+j; } return NULL; } 若不考虑正文至少有模式长的字串个数，且用字符指针编写，可简写成以下形式。 char *stringSearch(char *t, char *s) { char *q, *p; for(; *t != ‘\0’; t++) for(q = t, p = s; *p != ‘\0’ *q == *p; q++, p++) { } return *p == ‘\0’ ? t : NULL; } 目标 T S T U D E N S T U D E N T…… ‖‖ ‖‖ ‖ ‖ ? 模式 pat S T U D E N T 目标 T S T U D E N S T U D E N T…… ? 模式 pat S T U D E N T …… 目标 T S T U D E N S T U D E N T…… ‖‖ ‖‖ ‖ ‖ ‖ 模式 pat S T U D E N T 简单模式匹配的缺