数据结构课件第四

1、1第第4 4章章 串（串（StringString） 4.1 4.1 串类型的定义串类型的定义 4.2 4.2 串的表示和实现串的表示和实现 4.3 4.3 串的模式匹配算法串的模式匹配算法 课时安排：预计课时安排：预计4 4课时完成课时完成2数据结构课程的内容数据结构课程的内容3记为：记为： s = as = a1 1 a a2 2 . a . an n (n0 ) (n0 ) 串名串名串值（用串值（用 括起来）括起来）串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。4.1 4.1 串类型的定义串类型的定义隐含结束符隐含结束符00 ，即即ASCIIASCII码

2、码NULLNULL44.1 4.1 串类型的定义串类型的定义为何要单独讨论“串”类型？1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作）2） 程序设计中，处理对象很多都是串类型。5字符串若干术语字符串若干术语串长：串长：串中字符的个数（串中字符的个数（n0n0）. n=0 . n=0 时称为时称为空串空串 。空白串：空白串：由一个或多个由一个或多个空格符空格符组成的串。组成的串。问：空串和空白串有无区别？问：空串和空白串有无区别？答：答：有区别。有区别。 空串空串(Null String)(Null String)是指长度为零的串；是指长度为零的串； 空白串空白串(Blank Strin

3、g)(Blank String)，是指包含一个或多个空白字符，是指包含一个或多个空白字符 ( (空格键空格键) )的字符串。的字符串。6 子串：串S中任意个连续的字符序列叫S的子串; S叫主串。子串位置：子串的第一个字符在主串中的序号。字符位置：字符在串中的序号。串相等：串长度相等，且对应位置上字符相等。 字符串若干术语字符串若干术语7例例1 1：现有以下现有以下4 4个字符串：个字符串：a =BEI b =JING c = BEIJING d = BEI JING问：问： 它们各自的长度？它们各自的长度？a a是是c c和和d d的子串，在的子串，在c c和和d d中的位置都是中的位置都是1

4、 1 a a是哪个串的子串？在主串中的位置是多少？是哪个串的子串？在主串中的位置是多少？a =3，b =4，c = 7，d=8 “ “空串是任意串的子串；任意串空串是任意串的子串；任意串S S都是都是S S本身的子串，除本身的子串，除S S本本身外，身外，S S的其他子串称为的其他子串称为S S的真子串。的真子串。” ” 数据结构与算法数据结构与算法中山大学出版社中山大学出版社 空串是哪个串的子串？空串是哪个串的子串？ a a是不是自己的子串？是不是自己的子串？字符串举例字符串举例8C C语言中已有类似串运算函数！语言中已有类似串运算函数！ADT StringObjects: D=ai | a

5、iCharacterSet, i=1, 2,，n, n0Relations: R1= | ai-1,ai D, i=2, ，nfunctions: /至少有13种基本操作StrAssign(&T, chars) / 串赋值，生成值为chars的串TStrCompare(S,T) / 串比较，若ST，返回值大于0 StrLength(S) / 求串长，即返回串S中的元素个数 Concat(&T, S1, S2) / 串连接，用T返回S1S2的新串 SubString(&Sub, S, pos, len) / 求S中pos起长度为len的子串 Index(S, T, pos) /子串定位函数（模式

6、匹配），返回位置 Replace(&S, T,V) / 用子串V替换子串TADT String串的抽象数据类型定义串的抽象数据类型定义最最小小操操作作子子集集9复习：复习：C C语言中常用的串运算语言中常用的串运算 C语言语言串比较：串比较：int strcmp(char *s1,char *s2); 求串长：求串长：int strlen(char *s); 串连接：串连接：char strcat(char *to,char *from) 子串子串T定位定位：char strchr(char *s,char *c); 注：用注：用C C处理字符串时，要调用标准库函数处理字符串时，要调用标准库函

7、数 #include#include 类类CStrCompare(S,T) StrLength(S)Concat(&T, S1, S2)Index(S, T, pos)10Replace(&S, T,V) / / 用子串用子串V V替换子串替换子串T T例例1 1：设：设 s s = =I AM A STUDENTI AM A STUDENT, , t t = =GOODGOOD, , q q= =WORKERWORKER。求：。求：字符串操作字符串操作 StrLength(s) StrLength(t) SubString(&sub, s, 8, 7)= SubString(&sub, t,

8、 2, 1)= Index(s, A)= Index(s, t)=Replace( &s, STUDENT, q )=14 /参见参见P714STUDENTO30 （ s中没有中没有t=GOOD ！）！）Index(S, T, pos) / / 返回子串返回子串T T在在pospos之后的位置之后的位置I AM A WORKER11提问：提问： 当当s =I AM A STUDENT时时, INDEX（s,A，pos）=3，若想搜索后面那个，若想搜索后面那个A怎么办？怎么办？答答: 根据根据教材教材P71倒倒1行行的函数说明，的函数说明， INDEX（s,A）返回）返回的只是的只是“第一次第一

9、次”出现的位置。出现的位置。 如果还要搜索后面的如果还要搜索后面的A，则，则pos变量要跟着变才行。变量要跟着变才行。也就是说，要把得到的也就是说，要把得到的“第一次第一次”位置再代入位置再代入INDEX（ s,A，pos+1）函数中循环操作才行。）函数中循环操作才行。 字符串操作字符串操作12解：因为解：因为SubString(s,6,2)A ；SubString(s,7,8) STUDENTConcat(,t,SubString(s,7,8)GOOD STUDENT所以：所以：Concat(,SubString(s,6,2), Concat(t,SubString(s,7,8)A GOOD

10、 STUDENT例例2：设设 s =I AM A STUDENT, t =GOOD,求：求： Concat( SubString(s,6,2), Concat( t,SubString(s,7,8) ) ) ？字符串操作字符串操作134.24.2 串的表示和实现串的表示和实现首先强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。144.24.2 串的表示和实现串的表示和实现n定长顺序存储表示定长顺序存储表示用一组地址连续的存储单元存储串值的字用一组地址连续的存储单元存储串值的字符序列，属符序列，属静态存储静态存储方式。方式。n堆分配存储

11、表示堆分配存储表示用一组地址连续的存储单元存储串值的字用一组地址连续的存储单元存储串值的字符序列符序列, ,但存储空间是在程序执行过程中但存储空间是在程序执行过程中动态动态分配分配而得。而得。串的物理存储表示方法：串的物理存储表示方法：顺序顺序存储存储154.24.2 串的表示和实现串的表示和实现n串的块链存储表示串的块链存储表示链式方式存储链式方式存储串的物理存储表示方法：串的物理存储表示方法：链式链式存储存储16定长顺序存储特点：定长顺序存储特点：用一组连续的存储单元来存放串，直用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的接使用定长的字符数组来定义，数组的上界预先给出

12、上界预先给出，故，故称为称为静态存储静态存储分配。分配。例如：例如：#define Maxstrlen 255 /用户可用的最大串长用户可用的最大串长 typedef unsigned char SString Maxstrlen1 ; /P73 SString s; /s 是一个可容纳是一个可容纳255个字符的顺序串。个字符的顺序串。注：注：C C语言约定在串尾加结束符语言约定在串尾加结束符 00，以利操作加速，但不计，以利操作加速，但不计入串长；入串长；4.24.2 串的表示和实现串的表示和实现17例：例：用用顺序存储方式顺序存储方式编写编写求子串函数求子串函数SubStringSubSt

13、ring( (& &Sub,S,pos,lenSub,S,pos,len) ) 将串将串S S中从第中从第pospos个字符开始、长度为个字符开始、长度为lenlen的字符序列复制到串的字符序列复制到串SubSub中。（注：考虑到函数的通用性，应当让串中。（注：考虑到函数的通用性，应当让串SubSub的预留长度与的预留长度与S S一一样）样）s = a1 a2 . anposlenSub 4.24.2 串的表示和实现串的表示和实现18Status SubString(SString &sub, SString S, int pos, int len ) if(posS0 | lenS0-pos

14、+1) return ERROR; /若若pos和和len参数越界，则告警参数越界，则告警 Sub1len=Spospos+len-1; Sub0=len; return OK;子串长度子串长度讨论：想存放讨论：想存放超长超长字符串怎么办？字符串怎么办？改用改用动态分配动态分配的一维数组的一维数组堆堆例：例：用用顺序存储方式顺序存储方式编写编写求子串函数求子串函数SubStringSubString( (& &Sub,S,pos,lenSub,S,pos,len) ) 4.24.2 串的表示和实现串的表示和实现19思路思路：利用利用mallocmalloc函数合理预设串长空间。函数合理预设串长

15、空间。特点特点： 若在操作中串值改变，还可以利用若在操作中串值改变，还可以利用reallocrealloc函数函数按新串长度按新串长度增加空间增加空间（即动态数组概（即动态数组概念）念） 。堆分配存储特点：堆分配存储特点：仍用一组连续的存储单元来存放串，仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中但存储空间是在程序执行过程中动态分配动态分配而得。而得。4.24.2 串的表示和实现串的表示和实现20typedef struct char *ch; /若非空串若非空串,按串长分配空间按串长分配空间; 否则否则 /ch=NULL int length; /串长度串长度HString堆

16、堆T T的存储结构描述的存储结构描述T.chT.length4.24.2 串的表示和实现串的表示和实现21C C是指针变量，可以自增！是指针变量，可以自增！意即每次后移一个数据意即每次后移一个数据单元。单元。直到终值为直到终值为“假假”停停止，串尾特征是止，串尾特征是c c00NULLNULL0 0Status StrAssign(HString &T, char *chars) /生成一个串生成一个串T, TT, T值值串常量串常量charschars if (T.ch) free(T.ch); /释放释放T T原有空间原有空间 for (i=0, c=chars; ; +i, +c); /

17、求求charschars的串长度的串长度i i例例1 1：编写编写建堆建堆函数函数 ( (参见教材）参见教材）此处此处T.ch0T.ch0没有没有用来装串长，因为用来装串长，因为另有另有T.length T.length 分分量量if ( !i ) T.ch = NULL; T.length = 0;else if (!(T.ch = (char*)malloc( i *sizeof(char) exit(OVERFLOW); T.ch0.i-1 = chars0.i-1; T.length =i;Return OK; /StrAssign22Status Status StrInsertSt

18、rInsert ( HString ( HString & &S, int pos, S, int pos, HStringHString T ) T ) / /在串在串S S的第的第pospos个字符个字符之前之前（包括尾部）插入串（包括尾部）插入串T Tif (pos1if (posS.length+1) return ERROR; posS.length+1) return ERROR; /pos/pos不合法则告警不合法则告警 if(T.length)if(T.length) / /只要串只要串T T不空，就需要重新分配不空，就需要重新分配S S空间，以便插入空间，以便插入T T if

19、 (! if (!（S.chS.ch=(char=(char* *) )reallocrealloc( (S.chS.ch, , ( (S.length+T.length)S.length+T.length)* *sizeof(char) ) sizeof(char) ) exit(OVERFLOW); exit(OVERFLOW); / /若开不了新空间，则退出若开不了新空间，则退出 for ( i=S.length-1; i=for ( i=S.length-1; i=pos-1; pos-1; -i-i ) ) S.chS.chi+T.length = i+T.length = S.ch

20、S.chi; i; / / 为插入为插入T T而腾出而腾出pospos之后的位置，即从之后的位置，即从S S的的pospos位置起全部字符均后移位置起全部字符均后移 S.chS.ch pos-1pos-1pos+T.length-2 = T.chpos+T.length-2 = T.ch0 0T.lengthT.length-1 -1; ; / /插入插入T T，略，略/0/0 S.length S.length + =+ = T.length; T.length; / /刷新刷新S S串长度串长度 return OK; return OK; / /StrInsertStrInsert例例2

21、2：用用“堆堆”方式编写方式编写串插入函数串插入函数23讨论：法讨论：法1 1存储密度为存储密度为 ；法；法2 2存储密度为存储密度为 ；显然，若显然，若数据元素很多，用法数据元素很多，用法2 2存储更优存储更优称为称为块链结构块链结构链式存储特点链式存储特点 ：用链表存储串值，易插入和删除。用链表存储串值，易插入和删除。法法1 1：链表结点的数据分量长度取链表结点的数据分量长度取法法2 2：链表结点（数据域）大小取：链表结点（数据域）大小取n n( (例如例如n=4)n=4)1/21/29/15=3/59/15=3/5 A B C I NULLheadheadA B C D E F G H

22、I # # # NULL4.24.2 串的表示和实现串的表示和实现24对块链表的整体描述对块链表的整体描述#define CHUNKSIZE 80 /每块大小，可由用户定义typedef struct Chunk /首先定义结点类型 char ch CHUNKSIZE ; /每个结点中的数据域 struct Chunk * next ; /每个结点中的指针域Chunk; 块链类型定义块链类型定义typedef struct /其次定义用链式存储的串类型 Chunk *head; /头指针 Chunk *tail; /尾指针 int curLen; /结点个数 Lstring; /串类型只用一次

23、，前面可以不加Lstring对每个结点的描述25算法目的：确定主串中所含子串第一次出现的位置（定位） 4.3 4.3 串的模式匹配算法串的模式匹配算法（重点）（重点）定位问题称为串的模式匹配(Pattern Matching)，即子串定位运算， 它是串处理系统中最重要的操作之一。 典型函数为见教材264.3 4.3 串的模式匹配算法串的模式匹配算法（重点）（重点） BFBF算法算法 （又称古典的、经典的、朴素的、穷举的）（又称古典的、经典的、朴素的、穷举的） KMPKMP算法算法字符串模式匹配经典算法：字符串模式匹配经典算法：主串匹配指针带主串匹配指针带回溯，速度慢回溯，速度慢主串匹配指针避免

24、回溯，主串匹配指针避免回溯，匹配速度快，匹配速度快，274.3.1 BF4.3.1 BF算法的实现算法的实现即编写即编写Index(Index(S,T,posS,T,pos) )函数函数例例1： S=ababcabcacbab，T=abcac，pos=1， 求：串求：串T在串在串S中第中第pos个字符之后的位置。个字符之后的位置。 BFBF算法设计思想：算法设计思想：（1 1）将主串）将主串S S的第的第pospos个字符和模式个字符和模式T T的第的第1 1个字符比较，个字符比较， 若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符； 若若不等不等，从主串，从主串S S的下一字符（的

25、下一字符（pos+1pos+1）起，重新与）起，重新与T T第一个第一个字符比较。字符比较。 （2 2）直到主串）直到主串S S的一个连续子串字符序列与模式的一个连续子串字符序列与模式T T相等。返相等。返回值为回值为S S中与中与T T匹配的子序列匹配的子序列第一个字符的序号第一个字符的序号，即匹配成功。，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0 .0 .28Int (SString S, SString T, int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功 else return0;/

26、Index例例2 2： S S= =ababcabcacbab，T T= =abcac，求求相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的是被匹配的首个字符位置。i ij jS=a b a b c a b c a c b a bT=T=a b c a cpos=329 若若n n为主串长度，为主串长度，m m为子串长度，则串的为子串长度，则串的BFBF匹配算法最坏的匹配算法最坏的情况下需要比较字符的总次数为情况下需要比较字符的总次数为(n-m+1)*mO(n*m)一般的情况是：一般的情况是：O(O(n+mn+m) ) 推导方法：推导方法：BFBF算法的时间复杂度计算算法的时

27、间复杂度计算最好的情况是：一配就中！最好的情况是：一配就中！ 只比较了只比较了m m次。次。最恶劣情况是：主串前面最恶劣情况是：主串前面n-mn-m个位置都部分匹配到子串的最后个位置都部分匹配到子串的最后一位，即这一位，即这n-mn-m位比较了位比较了m m次，别忘了最后次，别忘了最后m m位也各比较了一次，位也各比较了一次，还要加上还要加上m m！所以总次数为：！所以总次数为：(n-m)(n-m)* *m+mm+m (n-m+1)(n-m+1)* *m m30BFBF算法的时间复杂度计算算法的时间复杂度计算能否利用已能否利用已部分匹配过部分匹配过的信息而加快模式串的滑动速度？的信息而加快模式

28、串的滑动速度？能！能！而且主串而且主串S S的指针的指针i i不必回溯不必回溯！最坏情况也能达到！最坏情况也能达到O(O(n+mn+m) )31KMPKMP算法（特点：速度快）算法（特点：速度快）KMPKMP算法设计思想算法设计思想KMPKMP算法的推导过程算法的推导过程KMPKMP算法的实现算法的实现 （关键技术（关键技术: :计算计算nextjnextj） next next值的含义值的含义KMPKMP算法的时间复杂度算法的时间复杂度4.3.2 KMP4.3.2 KMP算法算法32尽量利用已经尽量利用已经部分匹配部分匹配的结果信息，主串的结果信息，主串当前匹配位当前匹配位置置i i不要回溯

29、不要回溯，加快模式串的滑动速度。，加快模式串的滑动速度。1 1、KMPKMP算法设计思想算法设计思想（如何求子串新比较起点（如何求子串新比较起点k k）S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cIndex_kmpIndex_kmp的返回值应为的返回值应为i i=6=6i ii ii ik kk k a b aa b ck ki ii ii-T0i-T0 331 1、KMPKMP算法设计思想算法设计思

30、想（如何求子串新比较起点（如何求子串新比较起点k k）需要讨论两个问题：需要讨论两个问题：如何由如何由当前部分匹配结果当前部分匹配结果确定确定模式模式向右滑动向右滑动的新比较起点的新比较起点k k？ 模式应该向右滑多远才是高效率的模式应该向右滑多远才是高效率的? ?342 2、KMPKMP算法的推导过程：算法的推导过程：请抓住部分匹配时的两个特征：请抓住部分匹配时的两个特征：(1)(1)则则T T的的j-1j-1j-(k-1)j-(k-1)位位 S S前前位位 即即(4-2(4-2）式含义）式含义i ik kj j S=a b a b c a b c a c b a bT=T= a b c a

31、 c在在S S的的i i处和处和T T的第的第j j字符处失配字符处失配加速的前提：加速的前提：T T首与首与T Tj j之前处有相同子串之前处有相同子串S=a b a b c a b c a c b a bT=T=a b c a ci ik k则则T T的的k-1k-11 1位位S S前前位位 即即(4-3(4-3）式含义）式含义设主串目前打算与设主串目前打算与T的第的第k字符开始比较字符开始比较T1Tk-1在主串在主串i i处和模式串处和模式串j j处失处失配时，模式串配时，模式串k k处是下一处是下一次比较的新起点次比较的新起点(2)(2)352 2、KMPKMP算法的推导过程算法的推导

32、过程两式联立可得：加速的前提：T首与Tj之前处有相同子串注意：j 为当前已知的失配位置，我们的目标是计算新起点 k。式中仅剩一个未知数k，理论上已可解！36K=nextjK=nextj物理含义物理含义当主串在i处和模式串在j处失配时，主串下一次比较位置在失配位置处不变，保持为i，主串指针不用回朔；当主串在i处和模式串在j处失配时，nextj的含义是用模式串在nextj所在位置的字符和主串在i处的字符重新开始比较， nextj值越小，模式串向右移动越快。所以kmp算法的关键是如何求模式串所有位置的next值。37根据模式串根据模式串T T的规律：的规律： 由当前失配位置由当前失配位置j j( (

33、已知已知) ) ，可以，可以归纳归纳出计算新起点出计算新起点 k k的表达式。的表达式。next j 0 0 当当j j1 1时时 /不比较不比较max max k k | | 1kj 1kj 且且T T1 1TTk-1k-1=T Tj j-(k-1)-(k-1) T Tj j-1 -1 1 1 其他情况其他情况（1 1） next j next j 的物理意义是什么？的物理意义是什么？（2 2） next j next j 具体怎么求？具体怎么求？即即KMPKMP算法的实现算法的实现令令k k = = next j next j （k k 与与j j 显然具有函数关系），则显然具有函数关系）

34、，则取取T T首之后与首之后与TjTj处之前最处之前最大的相同子串大的相同子串新起点新起点 k k怎么求？怎么求？38（1 1） next j next j 有何物理意义？有何物理意义？nextjnextj函数值表征着模式函数值表征着模式T T中最大相同前缀子串和后缀子串中最大相同前缀子串和后缀子串（真子串）的长度为（真子串）的长度为k-1k-1。在实际应用中，在实际应用中，nextjnextj的值是当模式串在第的值是当模式串在第j j位失配时，用位失配时，用于匹配主串失配位的模式串位置于匹配主串失配位的模式串位置next j max k |1k1时，时，nextj的值为：模式串的位置的值为：

35、模式串的位置从从1到到j-1构成的串中所构成的串中所出现的出现的首尾相同的子串首尾相同的子串的最大长度的最大长度加加1。无首尾相同的子串时无首尾相同的子串时Nextj的值为的值为1。 / Nextj=1表示从模式串头部开始进行字符比较表示从模式串头部开始进行字符比较（2 2） nextjnextj怎么计算？怎么计算？怎样计算模式怎样计算模式T T所有可能的失配点所有可能的失配点 j j 所对应的所对应的 nextj？41从两头往中间比较从两头往中间比较 模模 式式 串串 T T： a b a a b a a a b c a c b c a c 可能失配位可能失配位 j j： 1 2 3 4 5

36、 6 7 81 2 3 4 5 6 7 8新匹配位新匹配位k=k=nextj nextj : 0 1 1 2 2 3 1 2 : 0 1 1 2 2 3 1 2 next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情况其他情况讨论：讨论：j=1时时, next j 0；/属于属于“j=1”情况情况;j=2时时, next j 1；/ 找不到找不到1kj的的k，属于，属于“其他情况其他情况”；刚才已归纳：刚才已归纳：j=3时时, k=2，只需查看，只需查看T1=T2 2成立否，成立否，No则属于其他情况则属于其他情况 j=4时时

37、, k=2，3，要查看要查看T T1 1= =T T3 3 及及T T1 1T T2 2= =T T2 2 T T3 3 是否成立是否成立j=5时时, k=2，3，4，要查看，要查看T1=T4 4 ，T1T2=T3 3T4 和和 T1T2T3 3=T2 2T3 3T4以此类推，可得后续以此类推，可得后续nextj值。值。可用演示程序验证可用演示程序验证nextjnextj与与s s无关，无关，可以预先计算可以预先计算例：例：42下一个要讨论的问题是：如何下一个要讨论的问题是：如何用递推方式用递推方式来求出最大相同子来求出最大相同子串的长度呢？换言之，如何让程序求出最大相同子串呢？这串的长度呢？

38、换言之，如何让程序求出最大相同子串呢？这个问题一旦解决，整个个问题一旦解决，整个KMPKMP算法就可以掌握得很透彻了。算法就可以掌握得很透彻了。递推法编程，参见教材程序递推法编程，参见教材程序（2 2） next j next j 怎么计算？怎么计算？43void get_next(SString T, int &next ) / /求模式串T的next函数值并存入数组next 。 i=1; next1=0; j=0; while(iT0 ) if(j= = 0|Ti= =Tj)+i; +j; nexti=j;else j=nextj; / get_next（2 2） next j next

39、j 怎么计算？怎么计算？44求解求解nextj流程图（递推）流程图（递推） i=1; j=0next1=0i1)f=n*fact(n-1); else f=1; return(f); 递推法：递推法：fact=1; for ( i=1; i=n; i+)fact*= i;例如：求例如：求f(n)=n!46第一步，先把模式T所有可能的失配点j 所对应的nextj计算出来；第二步：执行定位函数Index_kmp （与BF算法模块非常相似） KMP KMP算法的实现算法的实现即即Index( )Index( )操作的实现操作的实现Int Index_KMP(SString S, SString T,

40、 int pos) i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功 else return0;/Index_KMP47前面定义的前面定义的nextnext函数在某些情况下还是有缺陷的，函数在某些情况下还是有缺陷的，例如模式例如模式aaaabaaaab与主串与主串aaabaaaabaaabaaaab匹配时的情况：匹配时的情况：讨论：讨论： next j next j 是否完美无缺？是否完美无缺？ T：a a a a bj：1 2 3 4 5 nextj： 0 1 2 3 4先计算先计算nextj：48讨论：讨论： next j

41、next j 是否完美无缺？是否完美无缺？由此派生出next函数的改进算法此时效率不高的原因为：子串前此时效率不高的原因为：子串前4 4位相同时，主位相同时，主串字符若与其中一个不相等，则不必再与其余串字符若与其中一个不相等，则不必再与其余3 3个比个比较。而实际上还在依次比较。较。而实际上还在依次比较。S: a a a b a a a a b T: a a a a b i: 1 2 3 4 5 6 7 8 9 a a a a ba a a a ba a a a b似乎慢了一点？似乎慢了一点？能否再提速？能否再提速？a a a a b49void get_nextval(SString T, int &nextval ) /next/next函数修正值存入数组函数修正值存入数组nextvalnextvali=1; nextval1=0; j=0;while(iT0 ) if(j= = 0|Ti= =Tj ) +i;+j; if(Ti!=Tj ) ne