数据结构与算法 字符串

1、数据结构与算法数据结构与算法第三章第三章 字符串字符串主讲人主讲人 张铭张铭 :/北京大学信息科学与技术学院北京大学信息科学与技术学院网络与信息系统研究所网络与信息系统研究所版权所有，转载或翻印必究版权所有，转载或翻印必究主要内容主要内容n3.1 字符串抽象数据类型字符串抽象数据类型n3.2 字符串的存储结构和类定义字符串的存储结构和类定义n3.3 字符串运算的算法实现字符串运算的算法实现n3.4 字符串的模式匹配字符串的模式匹配字符串抽象数据类型字符串抽象数据类型 n3.1.1 基本概念基本概念n3.1.2 String抽象数据类型抽象数据类型3.1.1 基本概念基本概念n字符串，由字符串，

2、由0个或多个字符的顺个或多个字符的顺序排列所组成的复合数据结构，序排列所组成的复合数据结构，简称简称“串。串。n串的长度：一个字符串所包含的串的长度：一个字符串所包含的字符个数。字符个数。n空串：长度为零的串，它不包含空串：长度为零的串，它不包含任何字符内容。任何字符内容。字符串常数和变量字符串常数和变量n字符串常数字符串常数n例如：例如： nn字符串变量字符串变量3.1.1.2 字符字符n字符字符(char) ：组成字符串的基：组成字符串的基本单位本单位 。n在在C和和C中中n单字节单字节8 bitsn采用采用ASCII码对码对128个符号字个符号字符集符集charset进行编码进行编码 3

3、.1.1.3 字符的编码顺序字符的编码顺序 n为了字符串间比较和运算的便利，为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的字符编码表一般遵循约定俗成的“偏序编码规那么。偏序编码规那么。n字符偏序：根据字符的自然含义，字符偏序：根据字符的自然含义，某些字符间两两可以比较次序。某些字符间两两可以比较次序。n其实大多数情况下就是字典序其实大多数情况下就是字典序n中文字符串有些特例，例如中文字符串有些特例，例如“笔划笔划序序3.1.1.4 C+标准标准string n标准字符串：将标准字符串：将C+的的函数库作为字符串函数库作为字符串数据类型的方案。数据类型的方案。n例如：例如：char

4、SM;n串的结束标记：串的结束标记：0n0是是ASCII码中码中8位位BIT全全0码，码，又称为又称为NULL符。符。3.1.1.4 C+标准标准string(续续)n1. 串长函数串长函数 int strlen(char *s);n2. 串复制串复制 char *strcpy(char *s1, char*s2);n3串拼接串拼接 char *strcat(char *s1, char *s2);n4串比较串比较 int strcmp(char *s1, char *s2);3.1.1.4 C+标准标准string(续续)n5输入和输出函数输入和输出函数n6定位函数定位函数 char *st

5、rchr(char *s, char c);n7右定位函数右定位函数 char *strrchr(char *s, char c); 3.1.1.4 C+标准标准string(续续)3.1.2 String抽象数据类型抽象数据类型n字符串类字符串类class String：n不采用不采用char SM的形式的形式n而采用一种动态变长的存储结构。而采用一种动态变长的存储结构。3.1.2 String抽象数据类型抽象数据类型(续续)class String /字符串 类/它的存储结构和实现方法使用了C+标准string(简称标准串),/为了区别,类String所派生创建的实例对象,简称本串,或实例

6、串/在程序首,要#include 和#include 及/ 及 #include ，以及#include /1.字符串的数据表示：/字符串 S 通常用顺序存放，用数组S存储，元素的类型为char/字符串为变长，使用变量size记录串的当前长度/ 2.使用变量访问字符串：/字符串变量能参与运算,例如S1 + S2表示两个字符串首尾拼接在一起/用数组str存储字符串，在内部可以用stri访问串的第i个字符,/ 3.字符串类的运算集：请参看下面的成员函数private: public:char *str; /私有的指针变量，用于指向存储向量strsize+1int size；/本串的当前实际长度St

7、ring(char *s = ); /创建一个空的字符串String(char *s); / 创建新字符串，并将标准字符串s拷贝为初值String() / 销毁本串，从计算机存储空间删去本串/下面是算子的定义，包括赋值算子 拼接算子 和比较算子 等String& operator= (char *s）；/赋值操作=，标准串s拷贝到本串String& operator= (String& s）;/赋值操作=，串s复制到本串String operator (char *s）;/拼接算子，本串拼接标准串sString operator (String& s）；/拼接算子，本串拼接串sfriend S

8、tring operator+ (char *s1, String& s）；/友函数作为拼接算子+ 其返回值是一个实例串,等于标准串str拼接串s3.1.2.3 赋值算子、拼接算子赋值算子、拼接算子和比较算子和比较算子n赋值算子赋值算子n拼接算子拼接算子n比较算子比较算子 = != 和和 =3.1.2.4 输入输出算子输入输出算子 n输入算子输入算子n输出算子输出算子 3.1.2.5 处理子串处理子串(Substring)的函数的函数n简称简称“子串函数子串函数n提取子串提取子串n插入子串插入子串n寻找子串寻找子串n删除子串删除子串n3.1.2.6 字符串中的字符字符串中的字符n重载下标算子重

9、载下标算子 char& operator (int n);n按字符定位下标按字符定位下标 int Find(char c,int start);n反向寻找，定位尾部出现的字符反向寻找，定位尾部出现的字符 int FindLast(char c);3.2 字符串的存储结构字符串的存储结构和类定义和类定义n字符串的顺序存储字符串的顺序存储n字符串类字符串类class String的存储结的存储结构构字符串的顺序存储字符串的顺序存储n对于串长变化不大的字符串，可对于串长变化不大的字符串，可以有三种处理方案：以有三种处理方案：n1用用S0作为记录串长的存作为记录串长的存储单元。储单元。n缺点：限制了串

10、的最大长度不能缺点：限制了串的最大长度不能超过超过256。字符串的顺序存储字符串的顺序存储(续续) 2为存储串的长度，另辟一为存储串的长度，另辟一个存储的地方。个存储的地方。缺点：串的最大长度一般是静态缺点：串的最大长度一般是静态给定的，不是动态申请数组空间。给定的，不是动态申请数组空间。字符串的顺序存储字符串的顺序存储(续续) 3用一个特殊的末尾标记用一个特殊的末尾标记0。例如：例如：C+语言的语言的string函数库函数库include 采采用这一存储结构。用这一存储结构。3.2.2 字符串类字符串类class String的存储结构的存储结构n抽取子串函数抽取子串函数 例如：例如： St

11、ring s1 = value-; s2 = s1.Substr(2,3); 上述语句涉及的存储形式如下上述语句涉及的存储形式如下页所示。页所示。3.2.2 字符串类字符串类class String的存储结构的存储结构(续续)3.2.2 字符串类字符串类class String的存储结构的存储结构(续续)n微软微软VC的的CString类介绍类介绍n自动的动态存储管理，串的最大长度不超过自动的动态存储管理，串的最大长度不超过2GB n容器型容器型n不必使用不必使用new和和delete n使用特点：使用特点：n变量申明变量申明nCString s6( x, 6 ); / s6 = xxxxxx

12、nCString city = Philadelphia; / 串常数作为初值串常数作为初值n赋值语句赋值语句ns1 = s2 = hi there;n变量比较变量比较 if( s1 = s2 ) n方法调用方法调用 s1.MakeUpper(); n内部字符比较内部字符比较 if( s20 = h ) 3.3 字符串运算的算法实现字符串运算的算法实现n1. 串长函数串长函数 int strlen(char *s);n2. 串复制串复制 char *strcpy(char *s1, char*s2);n3串拼接串拼接 char *strcat(char *s1, char *s2);n4串比较

13、串比较 int strcmp(char *s1, char *s2);3.3.1 C+标准串运算的实现标准串运算的实现n【算法【算法3-1 】字符串的复制字符串的复制char *strcpy(char *d, char *s) /这个程序的毛病是，如果字符串这个程序的毛病是，如果字符串s比字符串比字符串d要长，要长，/这个程序没有检查拷贝出界，没有报告错误。这个程序没有检查拷贝出界，没有报告错误。/可能会造成可能会造成d的越界的越界 int i =0; while (si != 0) di = si; i+; di = 0; return d;3.3.1 C+标准串运算的实现标准串运算的实现(

14、续续)n【算法【算法3-2 】字符串的比较字符串的比较int strcmp( char *d, char *s) int i =0; while (si != 0 & di != 0 ) if (di si) return 1; else if (di = 0 & di != ch ); /当本串不含字符当本串不含字符ch，那么在串尾结束；，那么在串尾结束； /当成功寻找到当成功寻找到ch，返回该位置指针，返回该位置指针if (i = size) / 注意不是注意不是 index = size - 1n return temp; 3.3.2 String串运算的实现串运算的实现(续续) /假设

15、假设count超过自超过自index以右的实际子串长度，以右的实际子串长度， / 那么把那么把count变小变小if(count left ) count = left;/释放原来的存储空间释放原来的存储空间delete ; /张铭注释：注意此语句！张铭注释：注意此语句！/假设开辟动态存储空间失败，那么退出假设开辟动态存储空间失败，那么退出 = new char count+1; != 0)； /p的内容是一个指针，的内容是一个指针， /指向目前暂无内容的字符数组的首字符处指向目前暂无内容的字符数组的首字符处p = ; 3.3.2 String串运算的实现串运算的实现(续续) /q的内容是一个

16、指针，的内容是一个指针， /指向本实例串的指向本实例串的str数组的下标数组的下标index字符字符q = &strindex; /用用q指针取出它所指的字符内容后，指针加指针取出它所指的字符内容后，指针加1 / 用用p该指针所指的字符单元接受拷贝，该指针也加该指针所指的字符单元接受拷贝，该指针也加1for (i =0; i count; i+) *p+ = *q+; /循环结束后，让的结尾为循环结束后，让的结尾为0*p = 0; temp.size = count;return temp;3.3.2 String串运算的实现串运算的实现(续续)n【算法【算法 3-12 】查找字符】查找字符n

17、int String:Find(char c,int start)n n /在本实例字符串寻找字符在本实例字符串寻找字符c，如果找到，如果找到，那么那么/将其下标位置作为整数函数值返回，如将其下标位置作为整数函数值返回，如果果/c没有找到，那么为负值。参数没有找到，那么为负值。参数start是下是下标，标，/从从start下标开始寻找下标开始寻找c的工作的工作,假设假设start为为/0，那么从头寻找，那么从头寻找nint i = start;nassert( i size); 3.3.2 String串运算的实现串运算的实现(续续) /循环跳过那些不是循环跳过那些不是c的字符的字符while

18、 (stri != 0 & stri != c ) i+; /当本串不含字符当本串不含字符c，那么寻找到串尾结束，那么寻找到串尾结束， /返回返回1表示失败；当成功寻找到表示失败；当成功寻找到c，返回它的，返回它的 /下标位置下标位置if (stri = 0) / 注意：不要搞成注意：不要搞成“= = return -1; else return i ; 3.4 字符串的模式匹配字符串的模式匹配n模式匹配模式匹配(pattern matching)n一个目标对象一个目标对象S字符串字符串n一个模板一个模板patternP字符串字符串n任务：用给定的模板任务：用给定的模板P，在目标字符，在目标字

19、符串串S中搜索与模板中搜索与模板P全同的一个子串，全同的一个子串，并求出并求出S中第一个和中第一个和P全同匹配的子全同匹配的子串简称为串简称为“配串，返回其首配串，返回其首字符位置。字符位置。S s0 s1 sisi+1 si+2 si+m-2 si+m-1 sn-1 P p0 p1 p2 pm -2 pm-1 p0 p1 p2 pm-1 = si si+1 si+2 si+m-1朴素模式匹配朴素模式匹配S=ababababababbP=abababb X abababb X abababb X abababb X abababb X abababb X abababb 【算法【算法3-13

20、】模式匹配原始】模式匹配原始算法其一算法其一#include “ / 不是不是 #includeint FindPat_1(String S, String P, int startindex) / 从从S末尾倒数一个模板长度位置末尾倒数一个模板长度位置 int LastIndex = () - (); if (LastIndex startindex) return (-1); /g为为S的游标，用模板的游标，用模板P和和S第第g位置子串比较，位置子串比较， /假设失败那么继续循环假设失败那么继续循环 for (int g= startindex; g = LastIndex; g+) if

21、 ( P = S.Substr(g, () ) return g; /假设假设for循环结束，那么整个匹配失败，返回值为负，循环结束，那么整个匹配失败，返回值为负， return (-1); 3.4.1 模式匹配原始算法模式匹配原始算法(续续)【算法【算法3-13】模式匹配原始算法其二】模式匹配原始算法其二int FindPat_2(String S, String P,int startindex) / 从从S末尾倒数一个模板长度位置末尾倒数一个模板长度位置 int LastIndex = () - (); /开始匹配位置开始匹配位置startindex的值过大，匹配无法成功的值过大，匹配无

22、法成功 if (LastIndex startindex) return (-1); / i 是指向是指向S内部字符的游标，内部字符的游标， / j 是指向是指向P内部字符的游标内部字符的游标 int i=startindex, j = 0;3.4.1 模式匹配原始算法模式匹配原始算法(续续)/下面开始循环匹配下面开始循环匹配while (i LastIndex & j () / “ 可以吗？可以吗？ return (i - 1); else return -1; 3.4.1 朴素模式匹配朴素模式匹配 (纠错纠错)【算法【算法3-13】模式匹配原始算法纠错】模式匹配原始算法纠错int Find

23、Pat_2(String S, String P,int startindex) / 从从S末尾倒数一个模板长度位置末尾倒数一个模板长度位置 int LastIndex = () - P. strlen() ; /开始匹配位置开始匹配位置startindex的值过大，匹配无法成功的值过大，匹配无法成功 if (LastIndex startindex) return (-1); / i 是指向是指向S内部字符的游标，内部字符的游标， / j 是指向是指向P内部字符的游标内部字符的游标 int i=startindex, j = 0;3.4.1 朴素模式匹配纠错朴素模式匹配纠错(续续)/下面开始

24、循环匹配下面开始循环匹配while (i() & j() ) / “=呢？呢？ if( Pj = Si) i+; j+; else i = i - j + 1; j = 0; 错误错误1：如果：如果“i LastIndex，那么后面的就匹配不到。那么后面的就匹配不到。例如，例如，abababababb abababb ()=11，()=7，LastIndex = 4;“i = 4，j = 0, 匹配匹配a，接着，接着， “i = 5，j = 1就进行不了。就进行不了。错误错误2 2： 如果如果“j =()j = () ) / “ 可以吗？可以吗？ return (i - j); else re

25、turn -1; 错误错误3 3： 如果如果“j j ，其实匹配结束时，正好其实匹配结束时，正好j=P.size j=P.size 因为匹配最后一个字符后，还因为匹配最后一个字符后，还j+j+出错！出错！其实其实 “ “j = j = 就可以！就可以！错误错误4： return (i-1); 匹配完成后，匹配完成后，i i指向指向S S中最后一个字符的下一位，中最后一个字符的下一位，减去匹配串的长度，才是开始位。减去匹配串的长度，才是开始位。3.4.1 模式匹配原始算法模式匹配原始算法(续续)例如，例如，aaaaaaaaaab aaaaaab分析分析假定目标假定目标S的长度为的长度为n，模板，

26、模板P长度为长度为m， mn 在最坏的情况下，每一次循环都不成功，那么一共在最坏的情况下，每一次循环都不成功，那么一共要进行比较要进行比较n-m+1次次每一次每一次“相同匹配比较所耗费的时间，是相同匹配比较所耗费的时间，是P和和S逐逐个字符比较的时间，最坏情况下，共个字符比较的时间，最坏情况下，共m次。次。因此，整个算法的最坏时间开销估计为因此，整个算法的最坏时间开销估计为O(m n)。例例1， a a a a a a a a a a b a a a a a a b a a a a a a b a a a a a a b例例2， a b c d e f a b c d e f f a b c

27、d e f f a b c d e f f KMPKMP算法思想算法思想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 pj-2 p1 p2 pj-1 (2) 那么立刻可以断定那么立刻可以断定 p0 p1 pj-2 si-j+1 si-j+2 si-1 (朴素匹配的朴素匹配的)下一趟一定不匹配，可以跳过去下一趟一定不匹配，可以跳过去模式右滑模式右滑j-k位位模式右滑j

28、-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 pk3.4.2 字符串的特征向量字符串的特征向量Nn设模板设模板P由由m个字符组成：个字符组成： 记为记为P = q0 q1q2q3qm-1n令令特征向量特征向量N用于表示模板用于表示模板P的的字符分布特征，并简称字符分布特征，并简称N向量向量。它和它和P同长，由同长，由m个特征数个特征数n0 nm-1非负整数组成：非负整数组成： 记为记为N n0 n1n2n3nm-1 3.4.2 字符串的特征向量字符串的特征向量N(续续)n下面

29、说明下面说明ni的含义和它的递归定的含义和它的递归定义：义： 列出模板列出模板P开头的任意开头的任意t个字符，个字符，把它称为把它称为P的前缀子串。的前缀子串。 q0q1q2qt-1 3.4.2 字符串的特征向量字符串的特征向量N(续续) 在在P的第的第i位置的左边，也位置的左边，也取出取出t个字符，称为个字符，称为i位置的位置的左子串左子串。 qi-t+1.qi-2qi-1qi3.4.2 字符串的特征向量字符串的特征向量N(续续)n计算特征数计算特征数nin设法求出最长的设法求出最长的t最大的能最大的能够与前缀子串匹配的左子串简够与前缀子串匹配的左子串简称第称第i位的最长前缀串。位的最长前缀

30、串。nt就是要求的特征数就是要求的特征数ni。3.4.2 字符串的特征向量字符串的特征向量N(续续)n特征数特征数ni ( 0 ni i )是递归定义的，定义如是递归定义的，定义如下：下：n n00，n 对于对于i 1的的ni ，假定前一位置的特征数，假定前一位置的特征数ni-1 ，并且，并且ni-1 k ；n 如果如果qi qk ，那么，那么ni k1 ；n 当当qi qk 且且 k0时，时，n 那么那么 令令k n k -1 ;n 让让循环直到条件不满足；循环直到条件不满足；n 当当qi qk 且且 k 0时，那么时，那么 ni 0;3.4.2 字符串的特征向量字符串的特征向量N(续续)n

31、举例：举例：3.4.2 字符串的特征向量字符串的特征向量N(续续)3.4.2 字符串的特征向量字符串的特征向量N(续续)n【算法【算法3-14 】计算向量】计算向量Nnint *Next(String P)nn int m = (); /m为模板为模板P的长度的长度n assert( m 0); /假设假设m0，退出，退出n int *N = new intm; / 动态存储区开辟整数数动态存储区开辟整数数组组n assert( N != 0); /假设开辟存储区域失败，退出假设开辟存储区域失败，退出n N0 = 0;n for( int i =1 ; i 0 & Pi != Pk ) k =

32、 Nk-1; /根据根据Pi比较第比较第k位置前缀字符，决定位置前缀字符，决定Ni if(Pi = Pk) Ni = k+1; else Ni = 0 ; return N;3.4.3 KMP模式匹配算法模式匹配算法【算法【算法3-15 】KMP模式匹配算法模式匹配算法int KMP_FindPat(String S, String P, int *N, int startindex) /假定事先已经计算出假定事先已经计算出P的特征数组的特征数组N，作为输入参数，作为输入参数 / S末尾再倒数一个模板长度位置末尾再倒数一个模板长度位置 int LastIndex = S.size - P.si

33、ze; if (LastIndex - startindex) 0) return (-1); /startindex过大，匹配无法成功过大，匹配无法成功 int i; / i 是指向是指向S内部字符的游标，内部字符的游标， int j = 0; / j 是指向是指向P内部字符的游标，内部字符的游标，3.4.3 KMP模式匹配算法模式匹配算法(续续) / S游标游标i循环加循环加1 for (i = startindex; i 0) j = Nj-1; /Pj与与Si相同，继续下一步循环相同，继续下一步循环 if (P.strj = S.stri) j+; /匹配成功，返回该匹配成功，返回该S

34、子串的开始位置子串的开始位置 if( j = P.size) return (i - j +1); ; return (-1); /P和和S整个匹配失败，函数返回值为负整个匹配失败，函数返回值为负讨论：如果讨论：如果“i LastIndex，那么后面的就匹配不到。那么后面的就匹配不到。例如，例如，aaaaaaaaaab aaaaaab S.size=11，P.size=7，LastIndex = 4;“i = 4，j = 0, 匹配匹配a，接着，接着， “i = 5，j = 1就进行不了。就进行不了。KMP模式匹配例如一模式匹配例如一 0 1 2 3 4 5 6 P = a b a b a b b N =0 0 1 2 3 4 0 0 1 2 3 4 5 6 7 8 9 10 11 12S= a b a b a b a b a b a b b a b a b a b b X i=6,j=6, Nj-1=4 a b a b a b b X i=8, j=6, Nj-1 =4 a b a b a b b X i=10, j=6, j=4 a b a b a b b 0 1 2 3 4 5 6 7 8 9P = a a a a b a a a a cN =0 1 2 3 0 1