1、 第四章 串教学内容：教学内容：4.1 4.1 串及其基本运算串及其基本运算 4.2 4.2 串的定长顺序存储及基本运算串的定长顺序存储及基本运算 4.3 4.3 串的堆存储结构串的堆存储结构教学目的：教学目的：了解串的定义；了解串的定义；理解和领会串的存储方式；理解和领会串的存储方式；掌握常用的串运算。掌握常用的串运算。第四章 串教学重点：教学重点：串的基本概念、基本运算；串的基本概念、基本运算；串的两种存储方式。串的两种存储方式。串的模式匹配算法。串的模式匹配算法。教学难点：教学难点：串的模式匹配算法；串的模式匹配算法；串的基本运算的综合应用串的基本运算的综合应用4.1 4.1 串及其基本
2、运算串及其基本运算 串的基本概念串的基本概念 串的基本运算串的基本运算4.1.1 串的基本概念 串是由零个或多个任意串是由零个或多个任意字符组成的字符序列。字符组成的字符序列。s=s1 s2 sn。其中其中s 是串名；引号引起来的字符序列为串值，是串名；引号引起来的字符序列为串值，引号本身不属于串的内容；引号本身不属于串的内容；si(1=i=n)是一个任意字符，它称为串的元素，是一个任意字符，它称为串的元素，是构成串的基本单位，是构成串的基本单位，i是它在整个串中的序号是它在整个串中的序号;n为串的长度，表示串中所包含的字符个数，当为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通
3、常记为时，称为空串，通常记为。串是有限长的字符序串是有限长的字符序列列,由一对引号相括由一对引号相括,如如:a stringx=computery=student-1z=data structure串的定义串的定义 sa1a2an (n0)(1)值为空格字符串的空格串值为空格字符串的空格串(blank string)不等同空串不等同空串，它的长度为串中空格，它的长度为串中空格 字符的个数。字符的个数。(2)值为单个字符的字符串不等同单个字符。值为单个字符的字符串不等同单个字符。a ax=123 xx子串与主串：子串与主串：串中任意连续的字符组成的子序列称为该串串中任意连续的字符组成的子序列称为
4、该串的子串。包含子串的串相应地称为主串。的子串。包含子串的串相应地称为主串。子串的位置：子串的位置：子串的第一个字符在主串中的序号称为子串子串的第一个字符在主串中的序号称为子串的位置。的位置。串相等：串相等：称两个串是相等的，是指两个串的长度相等且称两个串是相等的，是指两个串的长度相等且对应字符都相等。对应字符都相等。A=BEI B=JING C=D=BEIJINGE=IJF=I J4.1.2 串的基本运算求串长求串长 StrLength(s)操作结果是求出串操作结果是求出串s的长度。的长度。StrLength(A)=3 StrLength(B)=4A=BEI B=JING 串赋值串赋值 St
5、rAssign(s1,s2)StrAssign(s1,s2)s1 s1是一个串变量，是一个串变量，s2s2或者是一个串常量，或者是一个串常量，或者是一个串变量（通常或者是一个串变量（通常s2s2是一个串常量时称是一个串常量时称为串赋值，是一个串变量称为串拷贝），操作为串赋值，是一个串变量称为串拷贝），操作结果是将结果是将s2s2的串值赋值给的串值赋值给s1s1，s1s1原来的值被覆原来的值被覆盖掉。盖掉。连接操作连接操作 StrConcat(s1,s2,s)或或 StrConcat(s1,s2)两个串的连接就是将一个串的串值紧接着放在两个串的连接就是将一个串的串值紧接着放在另一个串的后面，连接
6、成一个串。前者是产生新串另一个串的后面，连接成一个串。前者是产生新串s，s1和和s2不改变不改变;后者是在后者是在s1的后面联接的后面联接s2的串值，的串值，s1改变，改变，s2不改变。不改变。例如：例如：Concat(man,kind,S)求得求得 S=mankindS1=s1s2sm,S2=t1t2tnStrConcat(S1,S2)=s1s2smt1t2tn A=BEI B=JING C=D=BEIJINGstrConcat(A,B,S)，S=BEIJINGstrConcat(B,A,S)，S=JINGBEIstrConcat(A,B,S)strConcat(B,A,S)strConca
7、t(strConcat(A,B,S),D,S)=BEIJINGBEIJING=strConcat(A,strConcat(B,D,S),S)strConcat(s1，s2，sn，s)strConcat(strConcat(s1，sn-1，s)，sn，s)strConcat(strConcat(strConcat(s1，sn-2，s)，sn-1,s),sn,s)strConcat(strConcat(strConcat(s1，s2)，s3)，sn，s)StrLength(strConcat(s1,s2,sn)StrLength(s1)+StrLength(sn)求子串求子串 SubStr(s,i
8、,len)串串s存在并且存在并且1iStrLength(s)，0lenStrLength(s)-i+1。操作结果是求得从串操作结果是求得从串s的第的第i个字符开始的长度个字符开始的长度为为 len 的子串。的子串。len=0得到的是空串。得到的是空串。子串为子串为“串串”中的一个字符子序列中的一个字符子序列例如：例如：SubStr(commander,4,3)求得求得 man；SubStr(commander,1,9)求得求得 commander；SubStr(commander,9,1)求得求得 r；SubStr(D，1，3)=BEISubStr(D，4，0)SubStr(D，4，4)JIN
9、GD=BEIJINGSubStr(commander,4,7)sub=?SubStr(beijing,7,2)=?sub=?SubStr(student,5,0)=起始位置和子串长度之间存在约束关系起始位置和子串长度之间存在约束关系长度为长度为 0 的子串为的子串为“合法合法”串串串比较串比较 StrCmp(s1,s2)操作结果是若操作结果是若s1=s2，操作返回值为，操作返回值为0；若若s1s2，返回值，返回值s2，返回值，返回值0。例如：StrCompare(data,state)0子串定位子串定位 StrIndex(s,t)s为主串，为主串，t为子串，操作结果是若为子串，操作结果是若ts
10、，则操作返回则操作返回t在在s中首次出现的位置，否则返中首次出现的位置，否则返回值为回值为0。A=BEIB=JING C=D=BEIJINGE=IstrIndex(D，B)=4strIndex(D，C)=0strIndex(D，E)=3假设假设 S=abcaabcaaabc,T=bca strIndex(S,T,1)=2strIndex(S,T,3)=6strIndex(S,T,8)=0 “子串在主串中的位置子串在主串中的位置”意指子串意指子串中的第一个字符在主串中的位序。中的第一个字符在主串中的位序。串插入串插入 StrInsert(s,i,tStrInsert(s,i,t)串串s,ts,t
11、存在，且存在，且1iStrLength(s)+11iStrLength(s)+1。操。操作结果是将串作结果是将串t t插入到串插入到串s s 的第的第i i个字符位置个字符位置上，上，s s的串值发生改变。的串值发生改变。StrInsert(B,1,A)=BEIJING A=BEIB=JING例如：例如：S=chater，T=rac，则执行则执行 StrInsert(S,4,T)之后得到之后得到 S=character串删除串删除 StrDelete(s,i,lenStrDelete(s,i,len)串串s s存在，并且存在，并且1iStrLength(s)1iStrLength(s)，0le
12、nStrLength(s)-i+10lenStrLength(s)-i+1。操作结果是删。操作结果是删除串除串s s 中从第中从第i i个字符开始的长度为个字符开始的长度为lenlen的子的子串，串，s s的串值改变。的串值改变。StrDelete(BEIJING,1,3)=JING 串替换串替换 StrRep(s,t,rStrRep(s,t,r)串串s,t,rs,t,r存在且存在且t t不为空，操作结果是用不为空，操作结果是用串串r r替换串替换串s s中出现的所有与串中出现的所有与串t t相等的不重相等的不重叠的子串，叠的子串，s s的串值改变。的串值改变。例如：例如：假设假设 s=abc
13、aabcaaabca，t=bca若若 r=x，则经置换后得到则经置换后得到 s=axaxaax若若 r=bc，则经置换后得到则经置换后得到 s=abcabcaabcS=BBABBABBATABV=CStrRep(S，T，V)S=BBCBCBAS=BABABABABABT=BAB S=CACAC 串的基本操作中前个操作串的基本操作中前个操作(求串长、串赋值、串连接、求子串、串比较)是最为基本的，它们不是最为基本的，它们不能用其他的操作来合成，因此通常将这个基能用其他的操作来合成，因此通常将这个基本操作称为最小操作集。本操作称为最小操作集。即：这些操作不可能利用其他串操作来实现，即：这些操作不可能
14、利用其他串操作来实现，反之，其他串操作可在这个最小操作子集上实反之，其他串操作可在这个最小操作子集上实现。现。对于串的基本操作集可以有不同的定义对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。时，应以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如例如：C语言函数库中提供下列串处理函数：语言函
15、数库中提供下列串处理函数：例如，假设例如，假设 S=ZHONGGUO StrConcat(SubStr(S,1,5),SubStr(S,6,3)ZHONG GUOStrConcat(SubStr(S,1,2),SubStr(S,7,2)ZHUOD=BEIJINGSubStr(D,1,3)=NAND=NANJING 串的逻辑结构和线性表极为相似，区区别别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以大多以“单单个元素个元素”作为操作对象作为操作对象；在串的基本操作中，通常以通常以“串的整串的整体体”作为操作对象作为操作
16、对象。4.2 4.2 串的定长顺序存储及基本运算串的定长顺序存储及基本运算 串的定长顺序存储串的定长顺序存储 定长顺序串的基本运算定长顺序串的基本运算 模式匹配模式匹配4.2.1 4.2.1 串的定长顺序存储串的定长顺序存储 用一组地址连续的存储单元存储串值中的字用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256 char sMAXSIZE;则串的最大长度不能超过则串的最大长度不能超过256。非紧凑格式：非紧凑
17、格式：是一个存储单元是一个存储单元中只存放一个字符，中只存放一个字符，所需要的存储单元个所需要的存储单元个数就是串的长度。数就是串的长度。紧缩格式：紧缩格式：是在一个存储是在一个存储单元中存放多个字单元中存放多个字符。符。存储密度存储密度串值所占的存储字节串值所占的存储字节实际分配的存储字节实际分配的存储字节如何标识实际长度？如何标识实际长度？1.类似顺序表，用一个指针来指向最后一个字符。类似顺序表，用一个指针来指向最后一个字符。typedef struct char dataMAXSIZE;int curlen;SeqString;定义一个串变量：定义一个串变量：SeqString s;这种
18、存储方式可以直接得到串的长度：这种存储方式可以直接得到串的长度：s.curlen+1。2.在串尾存储一个不会在串中出现的特殊字符作为串的终在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如结符，以此表示串的结尾。比如C语言中处理定长串的方语言中处理定长串的方法就是这样的，它是用法就是这样的，它是用0来表示串的结束。这种存储方来表示串的结束。这种存储方法不能直接得到串的长度，是用判断当前字符是否是法不能直接得到串的长度，是用判断当前字符是否是0来确定串是否结束，从而求得串的长度。来确定串是否结束，从而求得串的长度。3.设定长串存储空间：设定长串存储空间：char sMA
19、XSIZE+1;用用s0存放串的实际存放串的实际长度，串值存放在长度，串值存放在s1sMAXSIZE，字，字符的序号和存储位置一致，应用更为方便。符的序号和存储位置一致，应用更为方便。4.2.2 4.2.2 定长顺序串的基本运算定长顺序串的基本运算 主要讨论定长串联接、求子串、串比较算法，主要讨论定长串联接、求子串、串比较算法，顺序串的插入和删除等运算基本与顺序表相同，顺序串的插入和删除等运算基本与顺序表相同，在此不在赘述。设串结束用在此不在赘述。设串结束用0来标识。来标识。基本操作在定长顺序存储上的实现基本操作在定长顺序存储上的实现 (1)串联接。串联接。S10+S20MAXSTRLEN S
20、10MAXSTRLEN S10MAXSTRLEN Status Concat(SString S1,SString S2,SString&T)/用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE，否则FALSE。return uncut;/Concat例如：例如：串的联接算法中需分三种情况处理：T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;if(S10+S20=MAXSTRLEN)/未截断 else if(S10 MAXSIZE-1)return 0;/*s长度不够长度不够*/j=0;while(s1j!=0)
21、si=s1j;i+;j+;j=0;while(s2j!=0)si=s2j;i+;j+;si=0;return 1;(2)求子串。求子串。算法思想。求子串的过程即为复制算法思想。求子串的过程即为复制字符序列的过程，将串字符序列的过程，将串S中从第中从第pos个个字符开始、长度为字符开始、长度为len的字符序列复制的字符序列复制到串到串Sub中。中。int StrSub(char*t,char*s,int i,int len)/*用用t返回串返回串s中第个中第个i字符开始的长度为字符开始的长度为len 的子串的子串1i串长串长*/int j;int slen;slen=StrLength(s);i
22、f(islen|lenslen-i+1)printf(参数不对参数不对);return 0;for(j=0;jlen;j+)tj=si+j-1;tj=0;return 1;串比较串比较 int StrCmp(char*s1,char*s2)int i=0;while(s1i=s2i&s1i!=0)i+;return(s1i-s2i);4.3 串的堆存储结构 串名的存储映象 堆存储结构 基于堆结构的基本运算4.3.1 串名的存储映象 串名的存储映象是串名串值内存分配对照表，也称串名的存储映象是串名串值内存分配对照表，也称为索引表。表的形式有多种表示，常见的串名串值存为索引表。表的形式有多种表示，
23、常见的串名串值存储映象索引表有如下几种：储映象索引表有如下几种：带串长度的索引表带串长度的索引表 末尾指针的索引表末尾指针的索引表 带特征位的索引表带特征位的索引表1.1.带串长度的索引表带串长度的索引表如图所示，索引项的结点类型为：如图所示，索引项的结点类型为：typedef struct char nameMAXNAME;/*串名串名*/int length;/*串长串长*/char*stradr;/*起始地址起始地址*/LNode;2.2.末尾指针的索引表末尾指针的索引表 如图所示，索引项的结点类型为：如图所示，索引项的结点类型为：typedef struct char nameMAXN
24、AME;/*串名串名*/char*stradr,*enadr;/*起始地址，末尾地址起始地址，末尾地址*/ENode;3.3.带特征位的索引表带特征位的索引表 当一个串的存储空间不超过一个指针的存储空间时，可当一个串的存储空间不超过一个指针的存储空间时，可以直接将该串存在索引项的指针域，这样既节约了存储空以直接将该串存在索引项的指针域，这样既节约了存储空间，又提高查找速度，但这时要加一个特征位间，又提高查找速度，但这时要加一个特征位tag以指出指以指出指针域存放的是指针还是串。针域存放的是指针还是串。如图所示，索引项的结点类型为：如图所示，索引项的结点类型为：typedef struct ch
25、ar nameMAXNAME;int tag;/*特征位特征位*/union/*起始地址或串值起始地址或串值*/char*stradr;char value4;uval;TNode;4.3.2 4.3.2 堆存储结构堆存储结构 在应用程序中，参与运算的串变量之间的长度相差较大，在应用程序中，参与运算的串变量之间的长度相差较大，并且操作中串值的长度变化也较大，因此为串变量预分配并且操作中串值的长度变化也较大，因此为串变量预分配固定大小的空间不尽合理。堆存储结构的基本思想是：在固定大小的空间不尽合理。堆存储结构的基本思想是：在内存中开辟能存储足够多的串、地址连续的存储空间作为内存中开辟能存储足够多
26、的串、地址连续的存储空间作为应用程序中所有串的可利用存储空间，称为堆空间，如设应用程序中所有串的可利用存储空间，称为堆空间，如设storeSMAX+1;根据每个串的长度，动态的为每个串在根据每个串的长度，动态的为每个串在堆空间里申请相应大小的存储区域，这个串顺序存储在所堆空间里申请相应大小的存储区域，这个串顺序存储在所申请的存储区域中，当操作过程中若原空间不够了，可以申请的存储区域中，当操作过程中若原空间不够了，可以根据串的实际长度重新申请，拷贝原串值后再释放原空间。根据串的实际长度重新申请，拷贝原串值后再释放原空间。如图所示，是一个堆结构示意图。阴影部分是已经为存如图所示，是一个堆结构示意图
27、。阴影部分是已经为存在的串分配过的，在的串分配过的，free为未分配部分的起始地址，每当向为未分配部分的起始地址，每当向sore中存放一个串时，要填上该串的索引项。中存放一个串时，要填上该串的索引项。4.3.3 4.3.3 基于堆结构的基本运算基于堆结构的基本运算 堆结构上的串运算仍然基于字符序列的复制进行，基堆结构上的串运算仍然基于字符序列的复制进行，基本思想是：当需要产生一个新串时，要判断堆空间中是本思想是：当需要产生一个新串时，要判断堆空间中是否还有存储空间，若有，则从否还有存储空间，若有，则从free指针开始划出相应大指针开始划出相应大小的区域为该串的存储区，然后根据运算求出串值，最小
28、的区域为该串的存储区，然后根据运算求出串值，最后建立该串存储映象索引信息，并修改后建立该串存储映象索引信息，并修改free指针。指针。设堆空间为：设堆空间为：char storeSMAX+1;自由区指针：自由区指针：int free;串的存储映象类型如下：串的存储映象类型如下：typedef struct int length;/*串长串长*/int stradr;/*起始地址起始地址*/HString;1.串常量赋值串常量赋值void StrAssign(HString*s1,char*s2)/*将一个字符型数组将一个字符型数组s2中的字符串送入堆中的字符串送入堆store中中,free是自
29、由区的指针是自由区的指针*/int i=0,len;len=StrLength(s2);if(len0|free+len-1SMAX)return 0;else for(i=0;iSMAX)return error;else for(i=0;ilength=s2.length;s1-stradr=free;free=free+s2.length;3.求子串求子串void StrSub(Hstring*t,Hstring s,int i,int len)/*该运算将串该运算将串s中第中第i个字符开始的长度为个字符开始的长度为len 的子串送到一个新串的子串送到一个新串t中中*/int i;if(
30、i0|lens.length-i+1)return error;else t-length=len;t-stradr=s.stradr+i-1;4.4.串联接串联接void Concat(HString s1,HString s2,HString*s)HString t;StrCopy(s,s1);StrCopy(&t,s2);s-length=s1.length+s2.length;以上堆空间和算法是由算法编写者自己设计和编写来实现的，在这里，重点介绍这种存储的处理思想，很多问题及细节尚未涉及，比如，废弃串的回收、自由区的管理问题等等。在常用的高级语言及开发环境中，大多数系统本身都提供了串的
31、类型及大量的库函数，用户可直接使用，这样会使算法的设计和调试更方便容易，可靠性更高。4.4 4.4 模式匹配模式匹配u串的模式匹配即子串定位是一种重要的串运算。很多串的模式匹配即子串定位是一种重要的串运算。很多软件，若有软件，若有“编辑编辑”菜单项的话，则其中必有菜单项的话，则其中必有“查找查找”子菜单项。子菜单项。u设设s和和t是给定的两个串，在主串是给定的两个串，在主串s中查找子串中查找子串t的过程称的过程称为为模式匹配模式匹配，如果在，如果在s中找到等于中找到等于t的子串，则称匹配成的子串，则称匹配成功，函数返回功，函数返回t在在s中的首次出现的存储位置中的首次出现的存储位置(或序号或序
32、号)，否，否则匹配失败，返回则匹配失败，返回0。t也称为也称为模式模式。u 为了运算方便，设字符串采用定长存储，且用第三种为了运算方便，设字符串采用定长存储，且用第三种方式表示串长，即串的长度存放在方式表示串长，即串的长度存放在0号单元，串值从号单元，串值从1号号单元存放，这样字符序号与存储位置一致。单元存放，这样字符序号与存储位置一致。算法思想如下：首先将算法思想如下：首先将s1与与t1进行比较，若不同，就将进行比较，若不同，就将s2与与t1进行比较，进行比较，.，直到，直到s的某一个字符的某一个字符si和和t1相同，再将它相同，再将它们之后的字符进行比较，若也相同，则如此继续往下比较们之后
33、的字符进行比较，若也相同，则如此继续往下比较，当，当s的某一个字符的某一个字符si与与t的字符的字符tj不同时，则不同时，则s返回到本趟开返回到本趟开始字符的下一个字符，即始字符的下一个字符，即si-j+2，t返回到返回到t1，继续开始下一趟，继续开始下一趟的比较，重复上述过程。若的比较，重复上述过程。若t中的字符全部比完，则说明本中的字符全部比完，则说明本趟匹配成功，本趟的起始位置是趟匹配成功，本趟的起始位置是i-j+1或或i-t0，否则，匹配，否则，匹配失败。失败。设主串设主串s=acabaabaabcacaabc，模式，模式t=abaabcac，匹配过程如图所示。，匹配过程如图所示。依据
34、这个思想，算法描述如下依据这个思想，算法描述如下:int StrIndex_BF(char*s,char*t)/*从串从串s的第一个字符开始找首次与串的第一个字符开始找首次与串t相等的子串相等的子串*/int i=1,j=1;while(i=s0&jt0)return(i-t0);/*匹配成功，返回存储位置匹配成功，返回存储位置*/else return 0;下面分析它的时间复杂度，设串下面分析它的时间复杂度，设串s长度为长度为n，串，串t长度为长度为m。匹配成功的情况下，考虑两种极端情况：匹配成功的情况下，考虑两种极端情况：在最好情况下，每趟不成功的匹配都发生在第一对字符比在最好情况下，每趟
35、不成功的匹配都发生在第一对字符比较时：较时：例如：例如：s=”aaaaaaaaaabc”，t=”bc”设匹配成功发生在设匹配成功发生在si处，则字符比较次数在前面处，则字符比较次数在前面i-1趟匹配趟匹配中共比较了中共比较了i-1次，第次，第i趟成功的匹配共比较了趟成功的匹配共比较了m次，所以总共次，所以总共比较了比较了i-1+m次，所有匹配成功的可能共有次，所有匹配成功的可能共有n-m+1种，设从种，设从si开始与开始与t串匹配成功的概率为串匹配成功的概率为pi，等概率情况下，等概率情况下pi=1/(n-m+1)，因此最好情况下平均比较的次数是：，因此最好情况下平均比较的次数是：即最好情况下
36、的时间复杂度是即最好情况下的时间复杂度是O(n+m)。在最坏情况下，每趟不成功的匹配都发生在t的最后一个字符：例如：s=”aaaaaaaaaaab”，t=”aaab”设匹配成功发生在si处，则在前面i-1趟匹配中共比较了(i-1)*m次，第i趟成功的匹配共比较了m次，所以总共比较了i*m次，因此最坏情况下平均比较的次数是：即最坏情况下的时间复杂度是O(n*m)。上述算法中匹配是从上述算法中匹配是从s串的第一个字符开始的，串的第一个字符开始的，有时算法要求从指定位置开始，这时算法的参数表有时算法要求从指定位置开始，这时算法的参数表中要加一个位置参数中要加一个位置参数pos：StrIndex(sh
37、ar*s,int pos,char*t)比较的初始位置定位在比较的初始位置定位在pos处。上面的算法是处。上面的算法是pos=1的情况。的情况。1.1.熟悉串的几种基本操作的定义，熟悉串的几种基本操作的定义，并能利用这些基本操作来实现串的并能利用这些基本操作来实现串的其它各种操作的方法。其它各种操作的方法。2.2.熟练掌握在串的定长顺序存储熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。结构上实现串的各种操作的方法。3.3.了解串的堆存储结构以及在其了解串的堆存储结构以及在其上实现串操作的基本方法。上实现串操作的基本方法。本章学习要点本章学习要点4.4.模式匹配是一个比较复杂的串操模式
38、匹配是一个比较复杂的串操作，是子串在主串中的定位操作。作，是子串在主串中的定位操作。简单的模式匹配算法比较直观，易简单的模式匹配算法比较直观，易于理解；但无回溯的模式匹配算法于理解；但无回溯的模式匹配算法的技巧性很强，读懂它需要费一定的技巧性很强，读懂它需要费一定的时间，不过一旦真正弄懂了这个的时间，不过一旦真正弄懂了这个算法，将会极大地增强你的学习兴算法，将会极大地增强你的学习兴趣。趣。5.5.理解串匹配的理解串匹配的KMPKMP算法，熟算法，熟悉悉NEXTNEXT函数的定义，学会手工计算函数的定义，学会手工计算给定模式串的给定模式串的NEXTNEXT函数值和改进的函数值和改进的NEXTNEXT函数值。函数值。
