北京大学：《数据结构与算法》课程教学资源（实验班讲义）第三章 字符串

主要内容 数据结构与算法 第三章字符串 31字符串抽象数据类型 32字符串的存储结构和类定义 张铭 33字符串运算的算法实现 http:/db.pku.edu.cn/mzhang/ds/ 北京大学信息科学与技术学院 34字符串的模式匹配 数据结构与算法教学小组 ⊙版权所有,转數或翻印必究 next 31字符串抽象数据类型 311基本概念 311基本概念 字符串,由0个或多个字符的顺 312 String抽象数据类型 序排列所组成的复合数据结构, 简称“串” m串的长度:一个字符串所包含的 字符个数。 空串:长度为零的串,它不包含 任何字符内容。 北京歌魏孔节了有,印究 大恤盒 张帖写 权质有,即鱼究 31.11字符串常数和变量 3112字符 字符串常数 字符(char):组成字符串的基 例如:" 本单位 ■字符串变量 在C和C++中 ■单字节(8bits) 采用AScI码对128个符号(字符 集 charset)进行编码 真大学健张帖写c所有,即必究 北太拳息单张帖权所者,即亮

1 数据结构与算法 第三章 字符串 张铭 http://db.pku.edu.cn/mzhang/DS/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 ©版权所有，转载或翻印必究 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 2 back next 主要内容 „ 3.1 字符串抽象数据类型 „ 3.2 字符串的存储结构和类定义 „ 3.3 字符串运算的算法实现 „ 3.4 字符串的模式匹配 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 3 back next 3.1字符串抽象数据类型 „ 3.1.1 基本概念 „ 3.1.2 String抽象数据类型 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 4 back next 3.1.1 基本概念 „ 字符串，由0个或多个字符的顺 序排列所组成的复合数据结构， 简称“串”。 „ 串的长度：一个字符串所包含的 字符个数。 „ 空串：长度为零的串，它不包含 任何字符内容。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 5 back next 3.1.1.1字符串常数和变量 „ 字符串常数 „ 例如： "\n" „ 字符串变量 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 6 back next 3.1.1.2 字符 „ 字符(char) ：组成字符串的基 本单位 。 „ 在C和C＋＋中 „ 单字节（8 bits） „ 采用ASCII码对128个符号（字符 集charset）进行编码

4314c+标准tng1314c+标准ng续 标准字符串:将C++的 1.串长函数 函数库作为字符串 int strlen(char *s)i 数据类型的方案。 char *strcpy(char *s1, char*s2); 例如: char s[M] ■3.串拼接 ■串的结束标记:"Y0 char *strcat(char *s1, char *s2); "\o是AsCI码中8位BTT全0码, 4.串比较 又称为NULL符 int strcmp(char *s1, char *s2); next 北京大单啦检写解有,究 3114C++标准 string(续) 312 String抽象数据类型 5.输入和输出函数 字符串类( class String) ■6.定位函数 ■不采用 char s[M]的形式 char strchr(char *s, char c); 而采用一种动态变长的存储结 ■7.右定位函数 构 char *strrchr(char *s, char c); 北京歌魏孔节了有,印究 张所有,赖 ass String /它的存储结构和实现方法使用了C++标准st 为了区别,类 String所派生创建的实例对象 char.tr://私有的指针变量,用于指向存储向量atr[aixe+1] 在程序首,要# include,以及# include String(hr咖="):/创建一个空的字符 ∥创建新字符串,并将标准字符率s持贝为初位 /1.字符串的数据表示 String0∥销數本串,从计算机存储空间删去本串 /字符串S通常用顺序存放,用数组S[]存储,元素的类型为char ∥下面是函数的定文,包捐赋值函数=拼换函数十和比较函敷〈等 /字符串为变长,使用变量size记录串的当前长度 String operators( char = s);/属值操作标准率持贝到本串 String operator=( String 5);/值操作,率复制到本率 ∥2.使用变量访问字符串 );/∥拼接函量十,本率拼接标准率 /字符串变量能参与运算,例如S1+S2表示两个字符串首尾拼接在一起 String operator+( String s);∥拼接函录十,本率拼按串 7/用数组strD存储字符串,在内部可以用str[访问串的第i个字符, end String operator+ ring s)1 友函教作为拼接函数+其返回值是一个实例串,等于标准串t拼接串 ∥/3.字符串类的运算集:请参看下面的成员函数 2

2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 7 back next 3.1.1.4 C++标准string „ 标准字符串：将C++的 函数库作为字符串 数据类型的方案。 „ 例如：char S[M]; „ 串的结束标记：'\0' „ '\0'是ASCII码中8位BIT全0码， 又称为NULL符。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 8 back next 3.1.1.4 C++标准string(续) „ 1. 串长函数 int strlen(char *s); „ 2. 串复制 char *strcpy(char *s1, char*s2); „ 3．串拼接 char *strcat(char *s1, char *s2); „ 4．串比较 int strcmp(char *s1, char *s2); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 9 back next 3.1.1.4 C++标准string(续) „ 5．输入和输出函数 „ 6．定位函数 char *strchr(char *s, char c); „ 7．右定位函数 char *strrchr(char *s, char c); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 10 back next 3.1.2 String抽象数据类型 „ 字符串类（class String）： „ 不采用char S[M]的形式 „ 而采用一种动态变长的存储结 构。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 11 back next 3.1.2 String抽象数据类型(续) class String //字符串 类 //它的存储结构和实现方法使用了C++标准string(简称标准串), //为了区别,类String所派生创建的实例对象,简称‘本串’,或‘实例串’ //在程序首,要#include 和#include 及 // 及 #include ，以及#include { //1.字符串的数据表示： //字符串 S 通常用顺序存放，用数组S[]存储，元素的类型为char //字符串为变长，使用变量size记录串的当前长度 // 2.使用变量访问字符串： //字符串变量能参与运算,例如S1 + S2表示两个字符串首尾拼接在一起 //用数组str[]存储字符串，在内部可以用str[i]访问串的第i个字符, // 3.字符串类的运算集：请参看下面的成员函数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 12 back next private: char *str; //私有的指针变量，用于指向存储向量str[size+1] int size； //本串的当前实际长度 public: String(char *s = ''); //创建一个空的字符串 String(char *s); // 创建新字符串，并将标准字符串s拷贝为初值 ~String() // 销毁本串，从计算机存储空间删去本串 //下面是函数的定义，包括赋值函数 ＝ 拼接函数 ＋ 和比较函数 < 等 String& operator= (char *s）；//赋值操作=，标准串s拷贝到本串 String& operator= (String& s）;//赋值操作=，串s复制到本串 String operator＋ (char *s）;//拼接函数＋，本串拼接标准串s String operator＋ (String& s）；//拼接函数＋，本串拼接串s friend String operator+ (char *s1, String& s）； //友函数作为拼接函数+ 其返回值是一个实例串,等于标准串str拼接串s

int operator>(istream istr, String s) 赋值操作符= riend Ostream& operator int Find( char c, Int start)://在本串中寻找字符c,从下标 start开始找, ∥/寻找到c后,返回字符c在本串的下标位置 ==和== //其他函数:求串长、判空串、清 nt IsEmpty o;//判本串为空串 void clear0:/清本串为空串 北京大单啦检写@有,翰 31.24输入输出操作符 3125处理子串( Substring) > 的函数 ■输入操作符>> ■简称“子串函数” 输出操作符<< 提取子串 插入子串 ■寻找子串 删除子串 nexy 大带_息 张写 积新有,神 张所有,赖 32字符串的存储结构圈 31.26字符串中的字符 和类定义 ■重载下标操作符[] ■321字符串的顺序存储 char& operator[](int n); ■322字符串类 class string的 ■按字符定位下标 存储结构 int Find(char c, int start; ■反向寻找,定位尾部出现的字符 int Find Last(char c; 北底大 张储帖写 真大带健意张写c所有,邮必究

3 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 13 back next //‘关系’函数，用于比较相等、大、小，例如 int operator>和> (isteream& istr,String& s）； friend ostream& operator >= != 和 == 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 15 back next 3.1.2.4 输入输出操作符 > „ 输入操作符>> „ 输出操作符<< 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 16 back next 3.1.2.5 处理子串(Substring) 的函数 „ 简称“子串函数” „ 提取子串 „ 插入子串 „ 寻找子串 „ 删除子串 „ … 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 17 back next 3.1.2.6 字符串中的字符 „ 重载下标操作符[] char& operator[] (int n); „ 按字符定位下标 int Find(char c,int start); „ 反向寻找，定位尾部出现的字符 int FindLast(char c); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 18 back next 3.2 字符串的存储结构 和类定义 „ 3.2.1字符串的顺序存储 „ 3.2.2字符串类class String的 存储结构

322字符串类 class string 321字符串的顺序存储 的存储结构(续) 用S[]作为记录串长的存储单元 微vc++的 CString类介绍 缺点:串的最大长度不能超过256 管理,串的最大长度不超过2GB ■另辟一个存储的地方存储串的长度 缺点:串的最大长度静态给定 使用特点: 变量申明 用一个特殊的末尾标记0 例如:C++语言的stri ring city=" Philadelphia";//串常敷作为初值 clude ) 2="hi there" 变量比较i(s1==s2) 方法调用 s1. MakeUpper(; 大卿血端张_·权,成 3字符串运算的算法实现 ■1.串长函数 int strcmp_1(char *d, char *s)t int strlen(char *s) for(int i=O; d[i]==s[i];++i)t ■2.串复制 f(d[i]==o&&s[i]==Y0) char *strcpy (char *s1, char*s2) return0;//两个字符串相等 3.串拼接 char *strcat(char *s1, char *s2) //不等比较第一个不同的字符 4.串比较 return(d[i-s[iD/abs(d[il-s[i]) nt strcmp(char *s1, char *s2); 大带_息 张写 积新有,神 张所有,赖 3.3字符串运算的算法实现 34字符串的模式匹配 ■331C++标准串运算的实现 ■模式匹配( pattern matching) ■332 String串运算的实现 个目标对象S(字符串) 一个模板( pattern)P(字符 任务:求出s中第一个与P全同 匹配的子串(简称为“配串”) 返回其首字符位置 北底大 张储帖写 真大带健意张写c所有,邮必究 e

4 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 19 back next 3.2.1字符串的顺序存储 „ 用S[0]作为记录串长的存储单元 „ 缺点：串的最大长度不能超过256 „ 另辟一个存储的地方存储串的长度 „ 缺点：串的最大长度静态给定 „ 用一个特殊的末尾标记'\0' „ 例如：C++语言的string函数库（＃ include ）采用这一存储 结构 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 20 back next 3.2.2 字符串类class String 的存储结构(续) „ 微软VC＋＋的CString类介绍 „ 自动的动态存储管理，串的最大长度不超过2GB „ 容器型 „ 不必使用new和delete „ 使用特点： „ 变量申明 „ CString s6( 'x', 6 ); // s6 = "xxxxxx" „ CString city = "Philadelphia"; // 串常数作为初值 „ 赋值语句 „ s1 = s2 = "hi there"; „ 变量比较 if( s1 == s2 ) „ 方法调用 s1.MakeUpper(); „ 内部字符比较 if( s2[0] == 'h' ) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 21 back next 3.3 字符串运算的算法实现 „ 1. 串长函数 int strlen(char *s); „ 2. 串复制 char *strcpy(char *s1, char*s2); „ 3．串拼接 char *strcat(char *s1, char *s2); „ 4．串比较 int strcmp(char *s1, char *s2); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 22 back next int strcmp_1(char *d, char *s) { for (int i=0;d[i]==s[i];++i ) { if(d[i]=='\0' && s[i]=='\0') return 0;//两个字符串相等 } //不等,比较第一个不同的字符 return (d[i]-s[i])/abs(d[i]-s[i]); } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 23 back next 3.3 字符串运算的算法实现 „ 3.3.1 C++标准串运算的实现 „ 3.3.2 String串运算的实现 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 24 back next 3.4 字符串的模式匹配 „ 模式匹配(pattern matching) „ 一个目标对象S（字符串） „ 一个模板（pattern）P（字符 串） „ 任务：求出S中第一个与P全同 匹配的子串（简称为“配串”）， 返回其首字符位置

34字符串的模式匹配 S551…s52…,sm25m1…Sn1 341朴素模式匹配 PPP…Pm-2Pm1 34.2字符串的特征向量N ■343KMP模式匹配算法 为使模式P与目标S匹配,必须满足 几nP… next 大卿血端张_·权,成 北京大单啦检写@有,赖职 朴素模式匹配 朴素模式匹配代码(简洁) b ababb int Find Pat_2(String S, String P, int startindex)t /g为S的游标,用模板P和S第g位置子串比较 /若失败则继续循环 翼 bb a bb for (int g= startindex; g<= Sstrlen(-Pstrlen O; or(int j=o;((<Pstrlen()&&(S[g+j]==PD) if G== P strlen) return g: return(-1);∥/for结東,或 startindex值过大则匹配失败 b I 大带_息 张写 张所有,赖 MMP算法思想 朴素模式匹配算法代价 5155+15+2 例如, aaaaaaaaaab n1…p2 ■目标S的长度为n,模板P长度为m,m≤n 则有ss152…5=阳P…P(1) 在類藝雞(每m不成功,则 朴素下一越 阳n…P21 如果%1…P2≠几1P2…1 时阁,相潭要知:个字符比校 则立刻可以断定 Po pi 整个算法的最坏时间开销估计为o(m·n) 朴素匹配的)下一趙一定不匹配,可以跳过去 Po p1 p2 next 北底大 张储帖写 真大带健意张写c所有,邮必究 5

5 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 25 back next S s0 s1 … si si+1 si+2 … si+m-2 si+m-1 … sn-1 ‖‖ ‖ ‖ ‖ P p0 p1 p2 … pm -2 pm-1 为使模式 P 与目标 S 匹配，必须满足 p0 p1 p2 …pm-1 = si si+1 si+2 … si+m-1 si si+1 si+2 … si+m-2 si+m-1 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 26 back next 3.4 字符串的模式匹配 „ 3.4.1 朴素模式匹配 „ 3.4.2 字符串的特征向量N „ 3.4.3 KMP模式匹配算法 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 27 back next 朴素模式匹配 S= P= a b a b a b a b a b a b b a b a b a b b a b a b a b b a b a b a b b Xa b a b a b b X X X a b a b a b bX Xa b a b a b b a b a b a b b 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 28 back next 朴素模式匹配代码（简洁） int FindPat_2(String S, String P, int startindex) { //g为S的游标，用模板P和S第g位置子串比较， //若失败则继续循环 for (int g= startindex; g <= S.strlen() - P.strlen(); g++) { for (int j=0; ((j<P.strlen()) && (S[g+j]==P[j])) ; j++) ; if (j == P.strlen()) return g; } return(-1); // for结束，或startindex值过大,则匹配失败 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 29 back next 朴素模式匹配算法代价 例如，aaaaaaaaaab aaaaaab „ 目标S的长度为n，模板P长度为m， m≤n „ 在最坏的情况下，每一次循环都不成功，则 一共要进行比较（n-m+1）次 „ 每一次“相同匹配”需要P和S逐个字符比较 的时间，最坏情况下，共m次 „ 整个算法的最坏时间开销估计为O(m • n) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 30 back next KMP算法思想 S s0 s1 … si-j-1 si-j si-j+1 si-j+2 … si-2 si-1 si … sn-1 ‖ ‖ ‖ ‖‖ P p0 p1 p2 … pj-2 pj -1 pj 则有 si-j si-j+1 si-j+2 … si-1 = p0 p1 p2 …pj-1 (1) p0 p1 p2 … pj-2 pj -1 如果 p0 p1 …pj-2 ≠ p1 p2 …pj-1 (2) 则立刻可以断定 p0 p1 …pj-2 ≠ si-j+1 si-j+2 … si-1 (朴素匹配的)下一趟一定不匹配，可以跳过去 p0 p1 p2 … pj-2 pj -1 朴素下一趟 × si pj

同样,若pP1…P3≠P2P3…1 再下一趟也不匹配,因为有 到对 值(首尾串长度),使得 模式右滑广位 乐5升+152…5k5k+1…515 P0p1…Pk≠PHk1P… 且 PP1…Pk-1=phkP+1…P1 PkPk1…1P 模式右滑j位PPM+1…PP Po pI 辆则/:=5k541…51m|辆 与≠,P==pk 北京大息 孔帖检写 342字符串的特征向量N 特征n的含义 设模板P由m个字符组成 aP的首子串qq1q2qt-1 记为P=qoq1q2q32…qm1 P的尾子串q+q12q1q1 ■特征向量N用于表示模板P的字符分 布特征 特征数n1 no n1n2n3…nm-1 最长的(t最大的)首尾子串能 m个非负整数 够匹配的t 大带_息 张写 积新有,神 张所有,赖 N=[23|o山23d 特征数n的递归定义 ①n=0, P=aalaabla aa 对于i>=1的n1,假定已知前一位置 的特征数n1,并且n1=k 前缀→ ②如果q=qk,则n=k+1; 前缀 ③当q≠q且k≠0时, 前缀→ 求特征向量N 则令k=n 前缀→ 让③循环直到条件不满足 ④当q≠q且k=0时,则n1=0 北底大 张储帖写 真大带健意张写c所有,邮必究 e 6

6 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 31 back next 同样，若 p0 p1 …pj-3 ≠ p2 p3 …pj-1 则再下一趟也不匹配，因为有 p0 p1 …pj-3 ≠ si-j+2 si-j+3 … si-1 直到对于某一个“k”值(首尾串长度)，使得 p0 p1 …pk ≠ pj-k-1 pj-k …pj-1 且 p0 p1 …pk-1 = pj-k pj-k+1 …pj-1 si-k si-k+1 … si-1 si ‖‖ ‖ pj-k pj-k+1 … pj-1 pj ‖‖ ‖ p0 p1 … pk-1 pk 模式右滑j-k位 × ? 则 p0 p1 …pk-1 = si-k si-k+1 … si-1 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 32 back next 模式右滑j-k位 si-j si-j+1 si-j+2 … si-k si-k+1 … si-1 si ‖ ‖‖ ‖ ‖ ‖ ‖ p0 p1 p2 … pj-k pj-k+1 … pj-1 pj ‖‖ ‖ p0 p1 … pk-1 pk × ? p0 p1 …pk-1 = si-k si-k+1 … si-1 si ≠ pj , pj ==pk? 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 33 back next 3.4.2 字符串的特征向量N „ 设模板P由m个字符组成： 记为P = q0 q1q2q3……qm-1 „ 特征向量N用于表示模板P的字符分 布特征 „ N ＝ n0 n1n2n3……nm-1 „ m个非负整数 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 34 back next 特征ni 的含义 „ P的首子串q0q1q2…qt-1 „ P的尾子串qi-t+1...qi-2qi-1qi „ 特征数ni „最长的（t最大的）首尾子串能 够匹配的t 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 35 back next 特征数ni 的递归定义 „ ① n0＝0， 对于i >= 1的ni ，假定已知前一位置 的特征数ni-1 ，并且ni-1＝ k ； „ ② 如果qi ＝ qk ，则ni ＝ k＋1 ； „ ③ 当qi ≠ qk 且 k≠0时， 则令k ＝ n k -1 ; 让③循环直到条件不满足； „ ④当qi ≠ qk 且 k ＝ 0时，则 ni ＝ 0; 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 36 back next 求特征向量N N = 2 3 0 1 2 P = a a a b a a a 0 12 3 4 5 6 a a c 789 3 4 0 前缀→ a 前缀→ a a 前缀→ a a a 0 1 前缀→ a 前缀→ a a 前缀→ a a a 前缀→ a a a a

求特征向量N(例2) 算法3-15】计算特征向量N ntm= P strlen(;//m为模板P的长度 P= ntm;∥/动态存储区开辟基数数组 前缀 ababa aaaa assert(NI=0);∥若开辟存储区域失败,返出 N[O]=0; for(inti=1;i0&& P[O]I= P[k]) tartine)t t(String S, String P, int*N, /假定事先已经计算出P的特征数组N,作为轴入参数 /根据P[]比较第k位量前缀字符,决定N[ if(P[]== Plk]) /s末尾再倒数一个模板长度位置 N[]=k+1; int LastIndex =Sstrlen()-Pstrlen N[]=0; eturn(-1);∥/ startindex过大,匹配无法成功 return N /i是指向s内部字符的游梅 】是指向P内部字符的游标,@e 大带_息 张写 积新有,神 张所有,赖 34.3KMP模式匹配算法效率 KMP模式匹配示例(一) ∥S游标循环加1 for(i startindex; i< Sstrlen (; i++)t /若当前位置的字符不同,则用N循环求当前的j, 用于将P的恰当位置与s的位置对准 =N[-1] /P[]与S[门]相同,继续下一步循环 6j=6,N1]=4 ==S[])j+ 匹配成功,返回该S子串的开始位置 labababs bi=B j=6, NU-1=4 if(j== Pstrlen) a|bab》l =10,j=6 9 return(-1);/P和整个匹配失败,函敷返回值为 b ab b 张储帖写 真大带健意张写c所有,邮必究

7 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 37 back next 求特征向量N(例2) N = 1 2 3 4 5 P = b a b a b a a 0 12 3 4 5 6 a c b 789 0 1 2 前缀→ a 0 0 a a a 3 1 1 b a b a a b 10 11 12 a a a 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 38 back next 【算法3-15 】计算特征向量N int *Next(String P) { int m = P.strlen(); //m为模板P的长度 assert( m > 0); //若m＝0，退出 int *N = new int[m]; // 动态存储区开辟整数数组 assert( N != 0); //若开辟存储区域失败，退出 N[0] = 0; for( int i =1 ; i 0 && P[i] != P[k] ) k = N[k-1]; //根据P[i]比较第k位置前缀字符，决定N[i] if(P[i] == P[k]) N[i] = k+1; else N[i] = 0 ; } return N; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 40 back next 【算法3-16】KMP模式匹配 int KMP_FindPat(String S, String P, int *N, int startindex) { //假定事先已经计算出P的特征数组N，作为输入参数 // S末尾再倒数一个模板长度位置 int LastIndex = S.strlen() - P.strlen(); if ((LastIndex - startindex) 0) j = N[j-1]; //P[j]与S[i]相同，继续下一步循环 if (P[j] == S[i]) j++; //匹配成功，返回该S子串的开始位置 if( j == P.strlen()) return (i - j +1); }; return (-1); //P和S整个匹配失败，函数返回值为负 } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 42 back next KMP模式匹配示例（一） S = a b a b a b a b a b a b b P = a b a b a b Xb √ a b a b a b Xb a b a b a b Xb a b a b a b b i=6,j=6, N[j-1]=4 i=8,j=6, N[j-1]=4 i=10, j=6, j’=4 P = a b a b a b b 0 12 3 4 5 6 N = 0 0 1 2 3 4 0 0 1 2 3 4 5 6 7 8 9 10 11 12

a a N=0 KMP算法的效率 s=tabla 两重循环 I=2=1,NU1]=0 afor循环最多执行n= S strlen(次 I=7」=4N1]=3 其内部的 while循环,最长循环 aa a 复a 次数是m= P strlen次 =8=4N1]=3 初看起来其时间开销也可能达 b aa a ac√ 到O(n×m) 大卿血端_权,究 京太盒帖写c有, a循环体中“j=N-1”语句的执行次 数不能超过加次。否则, 由手宁NH;”每执行一次必然使 另一种next数组方法 得j减少(至少减1) ■序号012345678 ■而使得j增加的操作只有“j++” a b c aa b a bc 那么,如果“jNi1;”的执行次数 k 00011212 超过n次,最终的结果必然使得为 负数。这是不可能的 p=p1?≠≠=≠=≠== m同理可以分析出求next数组的时间 nex-100-110200 为o(m) 因此,KMP算法的时间为o(n+m) nexy 大带_息 张写 积新有,神 张所有,赖 序号i012345678 序号i012345678 b a b HM匹配 P一P HM匹配 000112123 目标 aabcbabcaabcaababc 第1趟目标 aabcbabcaabcaababc caababc next(1=o 莫式 a kc aa b a bcagbabc nex4(3)=-1 第2趟目标 aabcbabcaabcaababc bcaa babc x next(6=2 abcnababc next(2=0 abcaababc 第3趟目标 aabelabcaabcaababe &beaab abc j 第4趙目标 aabcbabcaabcaababc abca 第5趙目标 aabcbabcaabcaababc 模式 (a bcaababe 北底大 张储帖写 中w

8 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 43 back next P = a a a b a a a 0 12 3 4 5 6 N = 0 1 2 3 0 1 2 3 4 0 a a c 789 S = a b a a a a a 0 12 3 4 5 6 a a b 789 a a a a c b 10 11 12 13 14 P = a a Xa a b a a a a c i=2, j=1, N[j-1]=0 i=2, j=2, N[j-1]=1 a a a a Xb a a a a c i=7, j=4, N[j-1]=3 a a a a Xb a a a a c i=8, j=4, N[j-1]=3 a a a a b a a a a c √ 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 44 back next KMP算法的效率 „ 两重循环 „ for循环最多执行n＝S.strlen()次 „ 其内部的while循环，最长循环 次数是m＝P.strlen()次。 „ 初看起来其时间开销也可能达 到O(n×m)。 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 45 back next „ 循环体中“j=N[j-1];”语句的执行次 数不能超过n次。否则， „ 由于“j= N[j-1];”每执行一次必然使 得j减少(至少减1) „ 而使得j增加的操作只有“j++” „ 那么，如果“j= N[j-1];”的执行次数 超过n次，最终的结果必然使得j为 负数。这是不可能的。 „ 同理可以分析出求next数组的时间 为O(m) „ 因此，KMP算法的时间为Ｏ(n+m) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 46 back next 另一种next数组方法 „ 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 pk==pi ? ≠ ≠ == ≠ == ≠ == == next[i] -1 0 0 -1 1 0 2 0 0 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 47 back next KMP匹配 目标 a a b c b a b c a a b c a a b a b c a b c a a b a b c a b c a a b a b c a b c a a b a b c a b c a a b a b c √ × „ 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 pk==pi ? ≠ ≠ == ≠ == ≠ == == next[i] -1 0 0 -1 1 0 2 0 0 next(1) = 0 × next(3) = -1 × next(6) = 2 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 48 back next KMP匹配 第1趟 目标 a a b c b a b c a a b c a a b a b c 模式 a b c a a b a b c next(0) = 0 第2趟 目标 a a b c b a b c a a b c a a b a b c 模式 a b c a a b a b c next(2)= 0 第3趟 目标 a a b c b a b c a a b c a a b a b c 模式 a b c a a b a b c j==0 第4趟 目标 a a b c b a b c a a b c a a b a b c 模式 a b c a a b a b c next(5) = 2 第5趟 目标 a a b c b a b c a a b c a a b a b c 模式 (a b) c a a b a b c √ × × × „ 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 3 ×

next数组对比 总结 序号i012345678 字符串抽象数据类型 a b c a ab c 字符串的存储结构和类定义 k 00011212 字符串运算的算法实现 p=p1?≠≠=≠=≠ ■字符申的模式匹配 next-100-110200 特征向量N及相应的KMP算法还有其 序号i012345678 .http:/www.db.pku.edu.cn/mzhan a b c a ab abc 000112123 大卿血端_权,究 北京大单啦检写@有,赖职 Thank you! 祝大家学习进步! http://db.pku.edu.cn/mzhang/ds/ 张铭: zhang@ db.pku. edu 大带_息 张写 积新有,神

9 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 49 back next next数组对比 „ 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 3 „ 序号i 0 1 2 3 4 5 6 7 8 P a b c a a b a b c k 0 0 0 1 1 2 1 2 pk==pi ? ≠ ≠ == ≠ == ≠ == == next[i] -1 0 0 -1 1 0 2 0 0 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 50 back next 总结 „ 字符串抽象数据类型 „ 字符串的存储结构和类定义 „ 字符串运算的算法实现 „ 字符串的模式匹配 „ 特征向量N及相应的KMP算法还有其 他变种、优化 „ http://www.db.pku.edu.cn/mzhan g/site/index.htm 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 51 back next Thank you! 祝大家学习进步！ http://db.pku.edu.cn/mzhang/DS/ 张铭：mzhang@db.pku.edu.cn