数据结构与算法第三部分字符串课件.ppt

《数据结构与算法第三部分字符串课件.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法第三部分字符串课件.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法第三部分字符串课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望主要内容主要内容n3.1字符串抽象数据类型字符串抽象数据类型n3.2字符串的存储结构和类定义字符串的存储结构和类定义n3.3字符串运算的算法实现字符串运算的算法实现n3.4字符串的模式匹配字符串的模式匹配北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1字符串抽象数据类型字符串抽象数据类型n3.1.1基本概念基本概念n3.1.2String

2、抽象数据类型抽象数据类型北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.1基本概念基本概念n字符串字符串，由，由0个或多个字符的顺个或多个字符的顺序排列所组成的复合数据结构，序排列所组成的复合数据结构，简称简称“串串”。n串的串的长度长度：一个字符串所包含的：一个字符串所包含的字符个数。字符个数。n空串空串：长度为零的串，它不包含：长度为零的串，它不包含任何字符内容。任何字符内容。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.1.1字符串常数和变量字符串常数和变量n字符串常数字符串常数n例如：

3、例如：nn字符串变量字符串变量北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.1.2字符字符n字符字符(char)：组成字符串的基：组成字符串的基本单位本单位。n在在C和和C中中n单字节（单字节（8bits）n采用采用ASCII码对码对128个符号（字符个符号（字符集集charset）进行编码）进行编码北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.1.3字符的编码顺序字符的编码顺序n为了字符串间比较和运算的便利，为了字符串间比较和运算的便利，字符编码表一般遵循约定俗成的字符编码表一般遵循约定俗

4、成的“偏序编码规则偏序编码规则”。n字符偏序字符偏序：根据字符的自然含义，：根据字符的自然含义，某些字符间两两可以比较次序。某些字符间两两可以比较次序。n其实大多数情况下就是字典序其实大多数情况下就是字典序n中文字符串有些特例，例如中文字符串有些特例，例如“笔划笔划”序序北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.1.4C+标准标准stringn标准字符串：将标准字符串：将C+的的函数库作为字符串函数库作为字符串数据类型的方案。数据类型的方案。n例如：例如：charSM;n串的结束标记：串的结束标记：0n0是是ASCII码中码中8位位BIT

5、全全0码，码，又称为又称为NULL符。符。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.1.4C+标准标准string(续续)n1.串长函数串长函数intstrlen(char*s);n2.串复制串复制char*strcpy(char*s1,char*s2);n3串拼接串拼接char*strcat(char*s1,char*s2);n4串比较串比较intstrcmp(char*s1,char*s2);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.1.4C+标准标准string(续续)n5输入

6、和输出函数输入和输出函数n6定位函数定位函数char*strchr(char*s,charc);n7右定位函数右定位函数char*strrchr(char*s,charc);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.1.4C+标准标准string(续续)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.2String抽象数据类型抽象数据类型n字符串类（字符串类（classString）：）：n不采用不采用charSM的形式的形式n而采用一种动态变长的存储结构。而采用一种动态变长的存储结构。北

7、京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.2String抽象数据类型抽象数据类型(续续)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.2.3赋值算子、拼接算子赋值算子、拼接算子和比较算子和比较算子n赋值算子赋值算子n拼接算子拼接算子n比较算子比较算子=!=和和=北京大学信息学院北京大学信息学院 版权所有，转载或翻

8、印必究版权所有，转载或翻印必究Page3.1.2.4输入输出算子输入输出算子n输入算子输入算子n输出算子输出算子北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.2.5处理子串处理子串(Substring)的函数的函数n简称简称“子串函数子串函数”n提取子串提取子串n插入子串插入子串n寻找子串寻找子串n删除子串删除子串n北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.1.2.6字符串中的字符字符串中的字符n重载下标算子重载下标算子char&operator(intn);n按字符定位下标按字符定位下标i

9、ntFind(charc,intstart);n反向寻找，定位尾部出现的字符反向寻找，定位尾部出现的字符intFindLast(charc);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.2字符串的存储结构字符串的存储结构和类定义和类定义n3.2.1字符串的顺序存储字符串的顺序存储n3.2.2字符串类字符串类classString的的存储结构存储结构北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.2.1字符串的顺序存储字符串的顺序存储n对于串长变化不大的字符串，可对于串长变化不大的字符串，可以有三种处

10、理方案：以有三种处理方案：（1）用）用S0作为记录串长的存储作为记录串长的存储单元。单元。n缺点：限制了串的最大长度不能缺点：限制了串的最大长度不能超过超过256。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.2.1字符串的顺序存储字符串的顺序存储(续续)（2）为存储串的长度，另辟一个）为存储串的长度，另辟一个存储的地方。存储的地方。n缺点：串的最大长度一般是静态缺点：串的最大长度一般是静态给定的，不是动态申请数组空间。给定的，不是动态申请数组空间。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.2.

11、1字符串的顺序存储字符串的顺序存储(续续)（3）用一个特殊的末尾标记）用一个特殊的末尾标记0。n例如：例如：C+语言的语言的string函数库函数库（include）采用）采用这一存储结构。这一存储结构。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.2.2字符串类字符串类classString的存储结构的存储结构n抽取子串函数抽取子串函数例如：例如：Strings1=value-;s2=s1.Substr(2,3);上述语句涉及的存储形式如下页上述语句涉及的存储形式如下页所示。所示。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所

12、有，转载或翻印必究Page3.2.2字符串类字符串类classString的存储结构的存储结构(续续)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.2.2字符串类字符串类classString的存储结构的存储结构(续续)n微软微软VC的的CString类介绍类介绍n自动的动态存储管理，串的最大长度不超过自动的动态存储管理，串的最大长度不超过2GBn容器型容器型n不必使用不必使用new和和deleten使用特点：使用特点：n变量申明变量申明nCStrings6(x,6);/s6=xxxxxxnCStringcity=Philadelphia;/串常

13、数作为初值串常数作为初值n赋值语句赋值语句ns1=s2=hithere;n变量比较变量比较if(s1=s2)n方法调用方法调用s1.MakeUpper();n内部字符比较内部字符比较if(s20=h)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.3字符串运算的算法实现字符串运算的算法实现n1.串长函数串长函数intstrlen(char*s);n2.串复制串复制char*strcpy(char*s1,char*s2);n3串拼接串拼接char*strcat(char*s1,char*s2);n4串比较串比较intstrcmp(char*s1,ch

14、ar*s2);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.3.1C+标准串运算的实现标准串运算的实现n【算法【算法3-1】字符串的复制字符串的复制char*strcpy(char*d,char*s)/这个程序的毛病是，如果字符串这个程序的毛病是，如果字符串s比字符串比字符串d要长，要长，/这个程序没有检查拷贝出界，没有报告错误。这个程序没有检查拷贝出界，没有报告错误。/可能会造成可能会造成d的越界的越界inti=0;while(si!=0)di=si;i+;di=0;returnd;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权

15、所有，转载或翻印必究Page3.3.1C+标准串运算的实现标准串运算的实现(续续)n【算法【算法3-2】字符串的比较字符串的比较intstrcmp(char*d,char*s)inti=0;while(si!=0&di!=0)if(disi)return1;elseif(di=0&di!=ch);/当本串不含字符当本串不含字符ch，则在串尾结束；，则在串尾结束；/当成功寻找到当成功寻找到ch，返回该位置指针，返回该位置指针if(i=size)/注意不是注意不是index=size-1returntemp;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page

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

17、str;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.3.2String串运算的实现串运算的实现(续续)/q的内容是一个指针，的内容是一个指针，/指向本实例串的指向本实例串的str数组的下标数组的下标index字符字符q=&strindex;/用用q指针取出它所指的字符内容后，指针加指针取出它所指的字符内容后，指针加1/用用p该指针所指的字符单元接受拷贝，该指针也加该指针所指的字符单元接受拷贝，该指针也加1for(i=0;icount;i+)*p+=*q+;/循环结束后，让循环结束后，让temp.str的结尾为的结尾为0*p=0;temp.siz

18、e=count;returntemp;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.3.2String串运算的实现串运算的实现(续续)n【算法【算法3-12】查找字符查找字符intString:Find(charc,intstart)/在本实例字符串寻找字符在本实例字符串寻找字符c，如果找到，则，如果找到，则/将其下标位置作为整数函数值返回，如果将其下标位置作为整数函数值返回，如果/c没有找到，则为负值。参数没有找到，则为负值。参数start是下标，是下标，/从从start下标开始寻找下标开始寻找c的工作的工作,若若start为为/0，则从头寻找

19、，则从头寻找inti=start;assert(isize);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.3.2String串运算的实现串运算的实现(续续)/循环跳过那些不是循环跳过那些不是c的字符的字符while(stri!=0&stri!=c)i+;/当本串不含字符当本串不含字符c，则寻找到串尾结束，则寻找到串尾结束，/返回返回1表示失败；当成功寻找到表示失败；当成功寻找到c，返回它的，返回它的/下标位置下标位置if(stri=0)/注意：不要搞成注意：不要搞成“=”return-1;elsereturni;北京大学信息学院北京大学信息学院

20、 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4字符串的模式匹配字符串的模式匹配n模式匹配模式匹配(patternmatching)n一个目标对象一个目标对象S（字符串）（字符串）n一个模板（一个模板（pattern）P（字符串）（字符串）n任务：用给定的模板任务：用给定的模板P，在目标字符，在目标字符串串S中搜索与模板中搜索与模板P全同的一个子串，全同的一个子串，并求出并求出S中第一个和中第一个和P全同匹配的子全同匹配的子串（简称为串（简称为“配串配串”），返回其首），返回其首字符位置。字符位置。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必

21、究PageS s0s1sisi+1si+2si+m-2si+m-1sn-1Pp0p1p2pm-2 pm-1为使模式为使模式为使模式为使模式 P P 与目标与目标与目标与目标 S S 匹配，必须满足匹配，必须满足匹配，必须满足匹配，必须满足p0p1p2pm-1=sisi+1si+2si+m-1北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page朴素模式匹配朴素模式匹配S=ababababababbP=abababbXabababbXabababbXabababbXabababbXabababbXabababb 北京大学信息学院北京大学信息学院 版权所有，转载

22、或翻印必究版权所有，转载或翻印必究Page【算法【算法3-13】模式匹配原始模式匹配原始算法（其一）算法（其一）#include“String.h”/不是不是#includeintFindPat_1(StringS,StringP,intstartindex)/从从S末尾倒数一个模板长度位置末尾倒数一个模板长度位置intLastIndex=S.strlen()-P.strlen();if(LastIndexstartindex)return(-1);/g为为S的游标，用模板的游标，用模板P和和S第第g位置子串比较，位置子串比较，/若失败则继续循环若失败则继续循环for(intg=startin

23、dex;g=LastIndex;g+)if(P=S.Substr(g,P.strlen()returng;/若若for循环结束，则整个匹配失败，返回值为负，循环结束，则整个匹配失败，返回值为负，return(-1);北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.1模式匹配原始算法模式匹配原始算法(续续)【算法【算法3-13】模式匹配原始算法（其二）模式匹配原始算法（其二）intFindPat_2(StringS,StringP,intstartindex)/从从S末尾倒数一个模板长度位置末尾倒数一个模板长度位置intLastIndex=S.s

24、trlen()-P.strlen();/开始匹配位置开始匹配位置startindex的值过大，匹配无法成功的值过大，匹配无法成功if(LastIndexstartindex)return(-1);/i是指向是指向S内部字符的游标，内部字符的游标，/j是指向是指向P内部字符的游标内部字符的游标inti=startindex,j=0;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.1模式匹配原始算法模式匹配原始算法(续续)/下面开始循环匹配下面开始循环匹配while(iLastIndex&jP.strlen()/“”可以吗？可以吗？return(i

25、-1);elsereturn-1;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.1朴素模式匹配朴素模式匹配(纠错纠错)【算法【算法3-13】模式匹配原始算法（纠错）模式匹配原始算法（纠错）intFindPat_2(StringS,StringP,intstartindex)/从从S末尾倒数一个模板长度位置末尾倒数一个模板长度位置intLastIndex=S.strlen()-P.strlen();/开始匹配位置开始匹配位置startindex的值过大，匹配无法成功的值过大，匹配无法成功if(LastIndexstartindex)return

26、(-1);/i是指向是指向S内部字符的游标，内部字符的游标，/j是指向是指向P内部字符的游标内部字符的游标inti=startindex,j=0;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.1朴素模式匹配纠错朴素模式匹配纠错(续续)/下面开始循环匹配下面开始循环匹配while(iS.strlen()&jP.strlen()/“=”呢？呢？if(Pj=Si)i+;j+;elsei=i-j+1;j=0;错误错误1：如果如果“iLastIndex”，那么后面的就匹配不到。那么后面的就匹配不到。例如，例如，abababababbabababbS.s

27、trlen()=11，P.strlen()=7，LastIndex=4;“i=4，j=0”,匹配匹配a，接着，接着，“i=5，j=1”就进行不了。就进行不了。错误错误2：如果如果“j=P.strlen()/“”可以吗？可以吗？return(i-j);elsereturn-1;错误错误3：如果如果“jP.strlen”，其实匹配结束时，正好其实匹配结束时，正好j=P.size j=P.size（因为匹配最后一个字符后，还（因为匹配最后一个字符后，还j+j+）出错！出错！其实其实 “j=P.strlen”就可以！就可以！错误错误4：return(i-1);匹配完成后，匹配完成后，i i指向指向S

28、S中最后一个字符的下一位，中最后一个字符的下一位，减去匹配串的长度，才是开始位。减去匹配串的长度，才是开始位。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.1模式匹配原始算法模式匹配原始算法(续续)例如，例如，aaaaaaaaaabaaaaaabn分析分析n假定目标假定目标S的长度为的长度为n，模板，模板P长度为长度为m，mnn在最坏的情况下，每一次循环都不成功，则一在最坏的情况下，每一次循环都不成功，则一共要进行比较（共要进行比较（n-m+1）次）次n每一次每一次“相同匹配相同匹配”比较所耗费的时间，是比较所耗费的时间，是P和和S逐个字符比

29、较的时间，最坏情况下，共逐个字符比较的时间，最坏情况下，共m次。次。n因此，整个算法的最坏时间开销估计为因此，整个算法的最坏时间开销估计为O(m n)。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page例例1，aaaaaaaaaabaaaaaab aaaaaabaaaaaab例例2，abcdefabcdeffabcdeff abcdeff北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究PageKMPKMP算法思想算法思想S s0s1si-j-1si-jsi-j+1si-j+2si-2-2si-1sisn-1 Pp0p1p

30、2pj-2-2pj-1 pj 则有则有则有则有si-j si-j+1si-j+2si-1=p0p1p2pj-1(1)如果如果如果如果 p0p1pj-2 p1p2pj-1 (2)则立刻可以断定则立刻可以断定则立刻可以断定则立刻可以断定 p0p1pj-2 si-j+1si-j+2si-1(朴素匹配的朴素匹配的朴素匹配的朴素匹配的)下一趟一定不匹配，可以跳过去下一趟一定不匹配，可以跳过去下一趟一定不匹配，可以跳过去下一趟一定不匹配，可以跳过去北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page同样，若同样，若 p0 p1 pj-3 p2 p3 pj-1则再下一趟

31、也不匹配，因为有则再下一趟也不匹配，因为有 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则则 p0 p1 pk-1=si-k si-k+1 si-1 si pj-k pj-k+1 pj-1 pj p0 p1 pk-1 pk 模式右滑模式右滑j-k位位北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page模式右滑j-k位 si-j si-j+1 si-j+2 s

32、i-k si-k+1 si-1 si p0p1p2pj-kpj-k+1pj-1 pj p0 p1 pk-1 pk北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.2字符串的特征向量字符串的特征向量Nn设模板设模板P由由m个字符组成：个字符组成：记为记为P=q0q1q2q3qm-1n令令特征向量特征向量N用于表示模板用于表示模板P的的字符分布特征，并简称字符分布特征，并简称N向量向量。它和它和P同长，由同长，由m个特征数个特征数n0nm-1非负整数组成：非负整数组成：记为记为Nn0n1n2n3nm-1北京大学信息学院北京大学信息学院 版权所有，转载

33、或翻印必究版权所有，转载或翻印必究Page3.4.2字符串的特征向量字符串的特征向量N(续续)n下面说明下面说明ni的含义和它的递归定的含义和它的递归定义：义：列出模板列出模板P开头的任意开头的任意t个字符，个字符，把它称为把它称为P的前缀子串。的前缀子串。q0q1q2qt-1北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.2字符串的特征向量字符串的特征向量N(续续)在在P的第的第i位置的左边，也位置的左边，也取出取出t个字符，称为个字符，称为i位置的位置的左子串左子串。qi-t+1.qi-2qi-1qi北京大学信息学院北京大学信息学院 版权所

34、有，转载或翻印必究版权所有，转载或翻印必究Page3.4.2字符串的特征向量字符串的特征向量N(续续)n计算特征数计算特征数nin设法求出最长的（设法求出最长的（t最大的）最大的）能够与前缀子串匹配的左子串能够与前缀子串匹配的左子串（简称（简称第第i位的最长前缀串位的最长前缀串）。）。nt就是要求的特征数就是要求的特征数ni。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.2字符串的特征向量字符串的特征向量N(续续)n特征数特征数ni(0nii)是递归定义的，定义如是递归定义的，定义如下：下：n00，对于对于i1的的ni，假定已知前一位置的特征

35、，假定已知前一位置的特征数数ni-1，并且，并且ni-1k；如果如果qiqk，则，则nik1；当当qiqk且且k0时，时，则则令令knk-1;让让循环直到条件不满足；循环直到条件不满足；当当qiqk且且k0时，则时，则ni0;北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.2字符串的特征向量字符串的特征向量N(续续)n举例：举例：北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.2字符串的特征向量字符串的特征向量N(续续)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻

36、印必究Page3.4.2字符串的特征向量字符串的特征向量N(续续)n【算法【算法3-14】计算向量计算向量Nint*Next(StringP)intm=P.strlen();/m为模板为模板P的长度的长度assert(m0);/若若m0，退出，退出int*N=newintm;/动态存储区开辟整数数组动态存储区开辟整数数组assert(N!=0);/若开辟存储区域失败，退出若开辟存储区域失败，退出N0=0;for(inti=1;i0&Pi!=Pk)k=Nk-1;/根据根据Pi比较第比较第k位置前缀字符，决定位置前缀字符，决定Niif(Pi=Pk)Ni=k+1;elseNi=0;returnN;北

37、京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.3KMP模式匹配算法模式匹配算法【算法【算法3-15】KMP模式匹配算法模式匹配算法intKMP_FindPat(StringS,StringP,int*N,intstartindex)/假定事先已经计算出假定事先已经计算出P的特征数组的特征数组N，作为输入参数，作为输入参数/S末尾再倒数一个模板长度位置末尾再倒数一个模板长度位置intLastIndex=S.size-P.size;if(LastIndex-startindex)0)return(-1);/startindex过大，匹配无法成功过大

38、，匹配无法成功inti;/i是指向是指向S内部字符的游标，内部字符的游标，intj=0;/j是指向是指向P内部字符的游标，内部字符的游标，北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page3.4.3KMP模式匹配算法模式匹配算法(续续)/S游标游标i循环加循环加1for(i=startindex;i0)j=Nj-1;/Pj与与Si相同，继续下一步循环相同，继续下一步循环if(P.strj=S.stri)j+;/匹配成功，返回该匹配成功，返回该S子串的开始位置子串的开始位置if(j=P.size)return(i-j+1);return(-1);/P和和S

39、整个匹配失败，函数返回值为负整个匹配失败，函数返回值为负讨论：讨论：如果如果“iLastIndex”，那么后面的就匹配不到。那么后面的就匹配不到。例如，例如，aaaaaaaaaabaaaaaabS.size=11，P.size=7，LastIndex=4;“i=4，j=0”,匹配匹配a，接着，接着，“i=5，j=1”就进行不了。就进行不了。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究PageKMP模式匹配示例（一）模式匹配示例（一）0123456P=abababbN=00123400123456789101112S=ababababababbabababb

40、Xi=6,j=6,Nj-1=4abababbXi=8,j=6,Nj-1=4abababbXi=10,j=6,j=4abababb 北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page0123456789P=aaaabaaaacN=012301234001234567891011121314S=aabaaaaaabaaaacbcaababcaaaabaaaacXi=2,j=2,Nj-1=1aaaabaaaacXi=2,j=1,Nj-1=0aaaabaaaacXi=7,j=4,Nj-1=3aaaabaaaacXi=8,j=4,Nj-1=3aaaabaaaac

41、北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page0123456789P=aaaabaaaacN=0121012340X(不是最长的，应该是不是最长的，应该是3)01234567891011121314S=aabaaaaaabaaaacbcaababcaaaabaaaacXi=2,j=2,Nj-1=1aaaabaaaacXi=2,j=1,Nj-1=0aaaabaaaacXi=7,j=4,Nj-1=1aaaabaaaac（错过了！）（错过了！）北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究PageKMP算法的效率算法的效

42、率n两重循环两重循环nfor循环最多执行循环最多执行nS.size次次n其内部的其内部的while循环，最长循环循环，最长循环次数是次数是mP.size次。次。n初看起来其时间开销也可能达初看起来其时间开销也可能达到到O(nm)。北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Pagen循环体中循环体中“j=Nj-1;”语句的执行语句的执行次数不能超过次数不能超过n次。次。否则，否则，n由于由于“j=Nj-1;”每执行一次必然使每执行一次必然使得得j减少减少(至少减至少减1)n而使得而使得j增加的操作只有增加的操作只有“j+”n那么，如果那么，如果“j=Nj-

43、1;”的执行次数的执行次数超过超过n次，最终的结果必然使得次，最终的结果必然使得j为为负数。这是不可能的。负数。这是不可能的。n同理可以分析出求同理可以分析出求next数组的时间数组的时间为为O(m)n因此，因此，KMP算法的时间为算法的时间为(n+m)北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page总结总结n字符串抽象数据类型字符串抽象数据类型n字符串的存储结构和类定义字符串的存储结构和类定义n字符串运算的算法实现字符串运算的算法实现n字符串的模式匹配字符串的模式匹配n特征向量特征向量N及相应的及相应的KMP算法还有其算法还有其他变种、优化他变种、优化nhttp:/ 版权所有，转载或翻印必究版权所有，转载或翻印必究Page优化优化例，例，aaaacaaaaaabaaaaaab aaaaaab北京大学信息学院北京大学信息学院 版权所有，转载或翻印必究版权所有，转载或翻印必究Page