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

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

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

字符串 (String) String)字符串是n 字符串是n ( ≥ 0 ) 个字符的有限序列,记 个字符的有限序列, 作 S : "c0c1c2…cn-1" 其中, 其中,S是串名字 "c0c1c2…cn-1"是串值 ci是串中字符 n是串的长度. 是串的长度. 如:"Welcome to Shanghai !!!"

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

在计算机非数值计算应用中, 在计算机非数值计算应用中,经常遇到字符序列的处 文字编辑,情报检索,自然语言翻译, 理.如,文字编辑,情报检索,自然语言翻译,事务 处理,图象处理等应用中经常遇到的那样. 处理,图象处理等应用中经常遇到的那样.在计算机 一个字符集上的每个字符用定长的代码表示, 中,一个字符集上的每个字符用定长的代码表示,所 有可能的各种字符都可以对应一个确定的代码. 有可能的各种字符都可以对应一个确定的代码.一个 特定的字符序列称为字符串,简称为串. 特定的字符序列称为字符串,简称为串.有两种方法 能比较方便地表示一个字符串. 能比较方便地表示一个字符串.一是人为地约定一个 特殊的代码为字符序列的结束符, 特殊的代码为字符序列的结束符,每个字符串最后都 有这个结束符.二是, 有这个结束符.二是,为每个字符序列另引入一个整 让该整数指出该字符串的字符个数. 数,让该整数指出该字符串的字符个数.本书采用第 一种表示字符串的方法

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

模式匹配是串的基本运算之一. 模式匹配是串的基本运算之一. 有两个字符串T S,字符串 称为正文, 字符串T 有两个字符串T和S,字符串T称为正文, 字符串S称为模式,要求找出模式S 字符串S称为模式,要求找出模式S在正文 中的首次出现的位置.一旦模式S T中的首次出现的位置.一旦模式S在正文 中找到,就说发生一次匹配. T中找到,就说发生一次匹配.有些应用 可能会要求找出所有的匹配位置. 可能会要求找出所有的匹配位置.

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

串的模式匹配定义 在串中寻找子串(第一个字 在串中寻找子串( 符)在串中的位置 在模式匹配中,子串称为模 词汇 在模式匹配中,子串称为模 串称为目标 目标. 式,串称为目标. Beijing" 示例 目标 T : "Beijing" jin" 模式 P : "jin" 匹配结果 = 3

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

记正文T的字符个数为n 记正文T的字符个数为n,令 T= t0t1t2…tn-1, 记模式S的字符个数为m 记模式S的字符个数为m,令 S= s0s1s2…sm-1. 若正文中自位置k开始有一次匹配, 若正文中自位置k开始有一次匹配,则有 sj = tk+j,0 <= j < m. m. 并且对所有p<k,没有对所有的0<=j<m, 并且对所有p<k,没有对所有的0<=j<m,m个等 式 sj = tp+j 全都成立. 全都成立.

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

7.1 简单匹配 第 1趟 第 2趟 第 3趟 第 4趟 T P T P T P T P abbaba aba abbaba aba abbaba aba abbaba aba √ 穷举的模式 匹配过程

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

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; }

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

若不考虑正文至少有模式长的字串个数,且用 若不考虑正文至少有模式长的字串个数, 字符指针编写,可简写成以下形式. 字符指针编写,可简写成以下形式. 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; '\ }

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

简单模式匹配的缺点: 简单模式匹配的缺点: 无谓比较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…… 目标 T

模式 pat S T U D E N T …… S T U D E N S T U D E N T…… 目标 T ‖‖ ‖‖ ‖ ‖ ‖ S T U D E N T 模式 pat

×

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

直接跳过子串可能错过成功比较F I F I F I Y U D E N T…… ‖‖ ‖‖ × 模式 pat F I F I Y 目标 T F I F I F I Y U D E N T…… ‖‖ × F I F I Y 模式 pat直接跳过错过成功比较

目标 T

目标 T

F I F I F I Y U D E N T…… ‖‖ ‖‖‖ F I F I Y 模式 pat

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

穷举的模式匹配算法时间代价: 穷举的模式匹配算法时间代价: 最坏情况比较n +1趟 趟比较m 最坏情况比较n-m+1趟,每趟比较m次, 总比较次数达( m+1)*m 总比较次数达(n-m+1)*m 原因在于每趟重新比较时 每趟重新比较时, 原因在于每趟重新比较时,目标串的检 测指针要回退. 测指针要回退.改进的模式匹配算法可 使目标串的检测指针每趟不回退. 使目标串的检测指针每趟不回退. 改进的模式匹配(KMP)算法的时间代价 算法的时间代价: 改进的模式匹配(KMP)算法的时间代价: 若每趟第一个不匹配,比较n-m+1趟, 若每趟第一个不匹配,比较n +1趟 总比较次数最坏达( )+m 总比较次数最坏达(n-m)+m = n 若每趟第m个不匹配, 若每趟第m个不匹配,总比较次数最坏亦 达到 n

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

7.2 KMP算法 算法

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

改进的模式匹配: 改进的模式匹配:寻找最大"跳跃" 寻找最大"跳跃"t0 t1 t2 …… tj-1 tj …… tn-1 ‖‖ ‖ ‖X 模式 pat p0 p1 p2 …… pj-1 pj …… pm-1 目标 T 模式 pat t0 t1 … tk … … tn-1 p0 p1 …… pm-2 pm-1 目标 T

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

T t0 … ts-1 ts ts+1 ts+2 … ts+j-1 ts+j ts+j+1 … tn-1 ‖ ‖ ‖ ‖ ‖ × P p0 p1 p2 … pj-1 pj pj+1 则有 ts ts+1 ts+2 … ts+j = p0 p1 p2 …pj 为使模式 P 与目标 T 匹配,必须满足 匹配,p0 p1 p2 …pj-1 …pm-1 = ts+1 ts+2 ts+3 … ts+j … ts+m

(1)

如果

p0 p1 …pj-1 ≠ p1 p2 …pj p0 p1 …pj-1 ≠ ts+1 ts+2 … ts+j

(2)

则立刻可以断定 下一趟必不匹配

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

同样,若 p0 p1 …pj-2 ≠ p2 p3 …pj 同样, 则再下一趟也不匹配, 则再下一趟也不匹配,因为有

p0 p1 …pj-2 ≠ ts+2 ts+3 … ts+j直到对于某一个" " 直到对于某一个"k"值,使得 且 则

p0 p1 …pk+1 ≠ pj-k-1 pj-k …pj

p0 p1 …pk = pj-k pj-k+1 …pj p0 p1 …pk = ts+j-k ts+j-k+1 … ts+j ‖ ‖ ‖ pj-k pj-k+1 … pj