第4章串主講教師:***時(shí)間:2025.07.01目錄CONTENTS01串的概念及ADT定義02串的定長順序存儲(chǔ)結(jié)構(gòu)及其算法實(shí)現(xiàn)03串的堆存儲(chǔ)結(jié)構(gòu)及其算法實(shí)現(xiàn)04串的模式匹配算法目錄CONTENTS串的概念及ADT定義4.14.1串的概念及ADT定義串(String)----零個(gè)或多個(gè)字符組成的有限序列。

串名串值串長n空串用Ф表示n=0單引號不是串的內(nèi)容，起標(biāo)識作用4.1串的概念及ADT定義子串與主串：一個(gè)串中任意個(gè)連續(xù)字符組成的子序列（含空串）稱為該串的子串，包含字串的串稱為主串。例如，“abcde”的子串有：“”、“a”、“ab”、“abc”、“abcd”和“abcde”等真子串是指不包含自身的所有子串?？崭翊河煽崭褡址麡?gòu)成的串稱為空格串。串常量與串變量：用引號引起來的一個(gè)字符序列稱為串常量，取值為串類型的變量稱為串變量。4.1串的概念及ADT定義串相等：兩個(gè)串的長度相等并且各個(gè)對應(yīng)位置上的字符都相同時(shí)。如：“abcd”≠“abc”“abcd”≠“abcde”所有空串是相等的。子串的位置：子串的第一個(gè)字符在主串中的序號稱為子串的位置。4.1串的概念及ADT定義串的基本運(yùn)算如下:

StrLength(s)：求串長。返回串s中字符個(gè)數(shù)。

StrAssign(&s，chars)：將字符串常量chars賦給串s，即生成其值等于chars的串s。

StrCopy(&T，S)：串復(fù)制。將串S賦給串T。

Concat(s，t)：串連接:返回由兩個(gè)串s和t連接在一起形成的新串

SubStr(s，i，j)：求子串。返回串s中從第i（1≤i≤n）個(gè)字符開始的、由連續(xù)j個(gè)字符組成的子串。

StrCmpare(S1，S2)：若S1等于S2，返回值為0；若S1<S2,返回值-1；若S1>S2,返回值1。4.1串的概念及ADT定義

StrIndex(S,T,pos)：串定位。找子串T在主串S中首次出現(xiàn)

InsStr(s1，i，s2)：插入。將串s2插入到串s1的第i（1≤i≤n+1）個(gè)字符中，即將s2的第一個(gè)字符作為s1的第i個(gè)字符，并返回產(chǎn)生的新串。

DelStr(s，i，j)：c刪除。從串s中刪去從第i（1≤i≤n）個(gè)字符開始的長度為j的子串，并返回產(chǎn)生的新串。

RepStr(s，i，j，t)：替換。在串s中，將第i（1≤i≤n）個(gè)字符開始的j個(gè)字符構(gòu)成的子串用串t替換，并返回產(chǎn)生的新串。4.1串的概念及ADT定義例如：用求串長StrLength、求子串SubString和串比較StrCompare實(shí)現(xiàn)串定位StrIndex()運(yùn)算。存在時(shí)，返回子串的位置。不存在，返回0。--檢測一個(gè)主串中是否存在一個(gè)給定的子串（模式）4.1串的概念及ADT定義初始條件1≤p≤StrLength(S)操作結(jié)果主串S中是否存在子串T：存在，返回S中的第p個(gè)字符之后T第一次出現(xiàn)的位置；不存在，返回0。4.1串的概念及ADT定義intStrIndex(StringS,StringT，intpos){intn,m,i;StringSub;n=StrLength(S);m=StrLength(T);i=pos;while(i<=n–m+1){Substring(Sub,S,i,m);if(StrCompare(Sub,T)!=0)++i;elsereturni;}return0;串的定長順序存儲(chǔ)結(jié)構(gòu)及其算法實(shí)現(xiàn)4.24.2.1串的定長順序存儲(chǔ)串中元素邏輯關(guān)系與線性表的相同，串可以采用與線性表相同的存儲(chǔ)結(jié)構(gòu)。邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)線性表順序表鏈表順序串鏈串4.2.1串的定長順序存儲(chǔ)#defineMaxSize256typedefstruct{chardata[MaxSize];intcurlen;}SString;用來存儲(chǔ)字符串用來指向最后一個(gè)字符1．用一個(gè)指針指示實(shí)際長度用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值中的字符序列，稱這種存儲(chǔ)結(jié)構(gòu)為順序串。4.2.1串的定長順序存儲(chǔ)例：串“Thisisadog.”的長度的表示方法：…Thisisadog.\0…14Thisisadog.…2.在串的存貯區(qū)首地址顯式地記錄串的長度。3.在串之后加結(jié)束標(biāo)志。如：PASCAL語言。如：C使用“\0”。4.2.2定長順序串的基本運(yùn)算順序串中實(shí)現(xiàn)串的基本運(yùn)算與順序表的基本運(yùn)算類似。詳細(xì)算法實(shí)現(xiàn)參見第2章順序表部分。以下算法：數(shù)組S[MAXSIZE+1]順序存儲(chǔ)串，其中S[0]存放串長，串結(jié)束符用＇\0＇標(biāo)識。4.2.2定長順序串的基本運(yùn)算（1）串連接StrConcat(s，t)

返回由兩個(gè)順序串s和t連接在一起形成的結(jié)果串。intStrConcat1(SString&T,SStringS1,S2,){T[1..S1[0]]=S1[1..S1[0]];//先復(fù)制串S1到T的前半部分switch{caseS1[0]+S2[0]<=MAXSIZE://不截?cái)?/p>

{T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];

T[0]=S1[0]+S2[0];//填寫T的長度

uncut=TRUE;break;}StrConcat"abcd""123""abcd123"4.2.2定長順序串的基本運(yùn)算caseS1[0]<MAXSIZE://截?cái)郤2{T[S1[0]+1..MAXSIZE]=S2[1..MAXSIZE–S1[0]];T[0]=MAXSIZE;uncut=FALSE;break;}caseS1[0]=MAXSIZE://不復(fù)制S2{T[0]=MAXSIZE;uncut=FALSE;break;}}returnuncut;}4.2.2定長順序串的基本運(yùn)算（2）求子串SubStringSString&T,SStringS,intpos,len)設(shè)源串為S，目標(biāo)串T（所取子串）。從S的第pos個(gè)字符開始，連續(xù)取len個(gè)字符復(fù)制到T中。intSubString(SString&T,SStringS,intpos,len)

{if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1

returnerror;T[1..len]=S[pos..pos+len-1];//截取子串T[0]=len;//填寫串長returnOK;}4.2.2定長順序串的基本運(yùn)算（3）串比較StrCompare(SStringS,T)intStrCompare(SStringS,T){inti=1;while(S[i]==T[i]&&S[i]!=’\0’&&T[i]!=’\0’)i++;return(S[i]-T[i]);}4.2.2定長順序串的基本運(yùn)算（4）串的逆置Strreverse(SString&S)串的逆置是指將串中的字符順序反過來?；舅悸肥菑膬深^到中間兩兩交換位置intStrreverse(SString&S){inti;for(i=1;i<=S[0]/2;i++)S[i]←→S[S[0]–i+1];returnOK;}串的堆存儲(chǔ)結(jié)構(gòu)及其算法實(shí)現(xiàn)4.34.3.1串的堆存儲(chǔ)結(jié)構(gòu)1.堆串

串的堆存儲(chǔ)結(jié)構(gòu)，與定長順序串的存儲(chǔ)結(jié)構(gòu)類似，都是用一維數(shù)組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串的字符序列，不同的是堆串的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配的。

在系統(tǒng)中存在一個(gè)稱為“堆”的自由存儲(chǔ)區(qū)，每當(dāng)建立一個(gè)新串時(shí)，可以通過動(dòng)態(tài)分配函數(shù)從這個(gè)空間中分配一塊實(shí)際串所需的存儲(chǔ)空間，來存儲(chǔ)新的串值。4.3.1串的堆存儲(chǔ)結(jié)構(gòu)#defineMaxStrLen255;typedefstruct{char*ch;//若串非空,則按串長分配存儲(chǔ)區(qū),//否則ch為NULLintlength;//串長度}HString;

2.堆串存儲(chǔ)結(jié)構(gòu)的定義4.3.1串的堆存儲(chǔ)結(jié)構(gòu)3.堆串存儲(chǔ)結(jié)構(gòu)的特點(diǎn)優(yōu)點(diǎn)：堆串存儲(chǔ)密度大，空間利用率高，可以動(dòng)態(tài)增長，隨機(jī)訪問。缺點(diǎn)：插入刪除需要移動(dòng)大量字符。4.3.2堆串的算法實(shí)現(xiàn)StatusInitString(HString&S)//串初始化,建立一個(gè)空串{S.ch=(char*)malloc(sizeof(char)*MAXSTRLEN);//申請串空間if(S.ch)exit(OVERFLEW);//堆空間大小不足分配失敗

else{S.length=0;returnOK};//分配成功}StatusInitString(HString&S)//串初始化,建立一個(gè)空串{S.ch=(char*)malloc(sizeof(char)*MAXSTRLEN);//申請串空間if(S.ch)exit(OVERFLEW);//堆空間大小不足分配失敗

else{S.length=0;returnOK};//分配成功}串的模式匹配算法4.44.4串的模式匹配算法算法目的：算法種類：AB確定主串中所含子串第一次出現(xiàn)的位置（定位）。BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法（特點(diǎn)：速度快）4.4.1簡單模式匹配算法S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci指針回溯——窮舉、經(jīng)典、古典算法4.4.1簡單模式匹配算法執(zhí)行循環(huán)：將主串的第p個(gè)字符和子串的第1個(gè)字符比較相等，繼續(xù)逐個(gè)比較后續(xù)字符；不等，回溯到主串的下一個(gè)字符，重新與子串的第1個(gè)字符比較。退出循環(huán)成功：返回S中與T匹配的子序列第1個(gè)字符的序號；失敗：返回0。BF算法步驟4.4.1簡單模式匹配算法

intStrIndex(SStrings,SStringT,intpos){i=pos;j=1; while(i＜=s[0]&&j＜=t[0]))

//兩個(gè)串均未到達(dá)串尾{if(s[i]==t[j]){i++;j++;}

//相等，繼續(xù)比較后續(xù)字符

else{i=i-j+2;;j=1;}

//不等，指針后退重新開始匹配}if(j＞t[0])returni-t[0];

//成功elsereturn0;

//失敗

}?i=i-j+2BF算法描述4.4.1簡單模式匹配算法S：aaaaabaT：aaaaaaaaabaaaba主串S長n，子串T長m?可能匹配成功的位置（1~)n-m+1aaaaabaaaaaaaaaaabaaaaabaaaaabaaaaban=7，m=5BF算法分析--算法分析4.4.1簡單模式匹配算法

每趟不成功的匹配都發(fā)生在T的第一個(gè)字符與S相應(yīng)字符的比較。第i個(gè)位置匹配成功，比較了（i-1+m）次假定每個(gè)位置上匹配成功的概率相等S：aaaaabaT：ba則平均比較次數(shù)最好情況下平均時(shí)間復(fù)雜度O(n+m)4.4.1簡單模式匹配算法

aaaaaabaabaaaaaabaab1234567aaaaaabaab第5個(gè)位置匹配成功比較了次？？？(5?1)*3+3=5*3=15——子串位于主串的末尾(i?1)*m+m=i*maaaaaabaabaaaaaabaabn=7，m=3最后一個(gè)位置匹配成功比較了次？？？(7?3)*3+3=5*3=15(n-m)*m+m=(n-m+1)*m4.4.1簡單模式匹配算法

每趟不成功的匹配都發(fā)生在T的最后一個(gè)字符與S相應(yīng)字符的比較第i個(gè)位置匹配成功，比較了i*m次假定每個(gè)位置上匹配成功的概率相等則平均比較次數(shù)最壞情況下平均時(shí)間復(fù)雜度O(n*m)（通常m<<n）4.4.2KMP算法《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第1卷基本算法》

《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第2卷半數(shù)值算法》《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第3卷排序與查找》《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第4卷組合算法》4.4.2KMP算法babcadcbcbcdijstBF缺陷：s的指針i回溯，已經(jīng)被檢索過的部分主串被重復(fù)檢索。同時(shí)，t的指針j也會(huì)回溯到起始位置。4.4.2KMP算法KMP改進(jìn)：如何避免指針i回溯。在BF中，指針i回溯的目的？不回溯可能會(huì)錯(cuò)過一些匹配。bcaaadcbcaadijst4.4.2KMP算法bcaaadcbcaadijst指針i不動(dòng)？子串向右滑動(dòng)，即找到j(luò)移動(dòng)的位置，使得新的指針j之前的字符能夠自動(dòng)匹配。4.4.2KMP算法j應(yīng)該移動(dòng)到的位置k有什么特點(diǎn)？abababcabaijstbckde4.4.2KMP算法abababcabaijstbckde

而滑動(dòng)之前已匹配過的字符能告訴我們什么信息呢？主串的k-1位后綴與子串的k-1位前綴相同！4.4.2KMP算法

abababcabaijstbcde

只需要比較子串的前后綴就可以了，無需主串！4.4.2KMP算法最長相同前綴和后綴4.4.2KMP算法

abajtbc

4.4.2KMP算法intStrIndex_KMP(SStrings,SStringt,intpos){

i=pos;j=1;while(i<=s[0]&&j<=t[0]){if(j==0||s[i]==t[j])i++;j++;}elsej=next[j];}if(j>t[0])returni-t[0];elsereturn0;}若s[i]和t[j]相等，則比較s[i+1]和t[j+1]若s[i]和t[j]不等，則j回退到next[j]所指的位置k，繼續(xù)比較s[i]和t[k]；當(dāng)s[i]和t[1]不等，則比較s[i+1]和t[1]所以next[1]=0。4.4.2KMP算法acabaabaaabbaaccab第一趟：從s[1]和t[1]開始匹配i=2主串模式串此時(shí)發(fā)生失配aabcacj12345678模式串a(chǎn)baabcacnext[j]01122312j=2，j=next[2]=1下一次將會(huì)進(jìn)行s[2]和t[1]的比較4.4.2KMP算法acabaabaaabbaaccab第二趟：從s[2]和t[1]開始匹配i=2模式串此時(shí)發(fā)生失配aabcacj=1,j=next[1]=0下一步將會(huì)進(jìn)行s[3]和t[1]的比較主串j12345678模式串a(chǎn)baabcacnext[j]011223124.4.2KMP算法acabaabaaabbaaccab第三趟：從s[3]和t[1]開始匹配模式串a(chǎn)abcac主串i=8發(fā)生失配j12345678模式串a(chǎn)baabcacnext[j]011223124.4.2KMP算法acabaabaaabbaaccab第四趟：從s[8]和t[3]開始匹配模式串a(chǎn)abcac主串i=8j=9(j>8,匹配成功）j12345678模式串a(chǎn)baabcacnext[j]011223124.4.2KMP算法失配時(shí)，i不變，j回退next[j]重新匹配。當(dāng)j退到0，i和j需要同時(shí)加1（即主串的第i個(gè)字符和模式的第1個(gè)字符不等時(shí)，應(yīng)從主串的第i+1個(gè)字符起重新進(jìn)行匹配)。4.4.2KMP算法若next[j]=k，子串起始的k-1個(gè)字符與j之前的k-1個(gè)字符匹配。next[j]存儲(chǔ)著指針j之前的字符信息，而與j所指字符無關(guān)。要保證j能夠回溯，應(yīng)該讓k<j，有j-k+1>1，j之前這一組字符最多從第二個(gè)開始。abajtbc

kfe4.4.2KMP算法j=2時(shí)，需要用到next[2]，意味著模式串已經(jīng)向右滑動(dòng)到j(luò)指向第2個(gè)字符，仍然不能與主串中i所指字符產(chǎn)生匹配。接下來需要讓指針j回溯到1，再進(jìn)行比較。此時(shí)會(huì)使用j=next[j]，而next[2]正是用來存儲(chǔ)需要回溯的位置，所以next[2]=1。aabdcijsabdt4.4.2KMP算法用肉眼求一些next[]數(shù)值1?????01123nextabcabcft4.4.2KMP算法已知next[j]=k，求next[j+1]的值當(dāng)t[j]==t[k]時(shí)，next[j+1]=next[j]+1，也就是k+1。只要j對應(yīng)的k是最大的，j+1對應(yīng)的k+1也必然是最大的。?4abcabcfj011123abc

tknext

k

j+14.4.2KMP算法已知next[j]=k，求next[j+1]的值當(dāng)t[j]!=t[k]時(shí)，想要找到j(luò)+1之前最長的字符匹配，應(yīng)該讓模式串起始部分向右滑動(dòng)到正確位置，然后對位置j的字符進(jìn)行比較。那么應(yīng)該滑動(dòng)到什么位置呢？?abcabafj011123abc

tknextkj+14.4.2KMP算法如果把這里的整個(gè)模式串看做主串，模式串的起始部分看做子串，這正是一個(gè)主串與模式串匹配的過程。尋找子串向右滑動(dòng)的位置，或者說指針k回溯的位置，這正是next[]數(shù)組的目的。答案顯而易見：k=next[k]。?abcabafj011123abc

tknextkj+14.4.2KMP算法通過比較發(fā)現(xiàn)t[j]==t[k]，那么next[j+1]就同樣會(huì)等于k+1，只不過現(xiàn)在的k已經(jīng)是回溯過后的。?2abcabafj011123abc

tknextkj+14.4.2KMP算法如果一次滑動(dòng)不行，那就繼續(xù)滑動(dòng)，繼續(xù)比較，可能直到滑動(dòng)到頭也沒能找到匹配。?abcabdfj011123abc

tknextkj+14.4.2KMP算法挨著j+1這個(gè)位置之前，完全找不到任何能與起始部分匹配的字符。如果在j+1這個(gè)位置失配，即使不回溯i，也不會(huì)出現(xiàn)錯(cuò)過匹配的現(xiàn)象，直接從模式串的第一個(gè)位置開始匹配即可。next[j+1]=1，此時(shí)k=0，next[j+1]=k+1。?1abcabdfj011123abc

tknextkj+14.4.2KMP算法因?yàn)閚ext[j]=k代表了j需要回溯的位置，所以j一定大于k。而在可能會(huì)進(jìn)行的多次k=next[k]過程中，假設(shè)next[k]=k1，next[k1]=k2……同理可得j>k>k1>k2……只要知道了j+1之前的所有位置的next[]數(shù)值，就一定可以求出next[j+1]的數(shù)值。?abcabdfj011123abc

tknextkk1k21j+14.4.2KMP算法voidget_next(char

*t,intnext[]){

inti=1,j=0;next[1]=0;while(i<t[0]){if(j==0||t[i]==t[j]){++i;++j;next[i]=j;}elsej=next[j];}}t[i]=t[j],next[i+1]=j+1;//初始化求出next[1]=0，next[2]=1這兩個(gè)特殊起始位置的數(shù)值。通過循環(huán)，可以求出next[3]、next[4]……最終求出整個(gè)next[]數(shù)組。在這個(gè)過程中模式串t，既做了主串又做了模式串，求next[]的過程還是一個(gè)模式匹配的問題。t[i]≠t[j],j往前滑動(dòng)到next[j]所指向的位置重復(fù)上述過程直到t[i]=t[j]；若找不到，j最終會(huì)滑到0，next[i+1]=1。4.4.2KMP算法以abaabc為例跟蹤程序運(yùn)行結(jié)果j=0—>i=2,j=1,next[2]=1下一步進(jìn)行t[2]和t[1]的比較abaabcabaabc主串模式串t[2]≠t[1],j=next[1]=0——>j=1，i=3，next[3]=1;下一次將會(huì)進(jìn)行t[3]和t[1]的比較。while(i<t[0]){if(j==0||t[i]==t[j]){++i;++j;next[i]=j;}elsej=next[j];4.4.2KMP算法while(i<t[0]){if(j==0||t[i]==t[j]){++i;++j;next[i]=j;}elsej=next[j];t[3]和t[1]的比較abaabcabaabc主串模式串t[3]=t[1]——>i=4,j=2,next[4]=2;下一步進(jìn)行t[4]和t[2]的比較。t[4]≠t[2]——>j=next[2]=1;下一步進(jìn)行t[4]和t[1]。4.4.2KMP算法while(i<t[0]){if(j==0||t[i]==t[j]){++i;++j;next[i]=j;}elsej=next[j];t[4]和t[1]的比較abaabcabaabc主串模式串t[4]=t[1]——>i=5,j=2,next[5]=2，下一步t[5]和t[2]會(huì)進(jìn)行比較。t[5]=t[2]——>i=6，j=3,next[6]=3i=t[0]循環(huán)結(jié)束4.4.2KMP算法求next[k+1]，其中k+1=17j1234567891011121413151617k+1pnext[j]4.4.2KMP算法已知next[16]=8，則元素有以下關(guān)系：j1234567891011121413151617k+1Pnext[j]若P8=P16，則next[17]=8+1=9這兩部分重合4.4.2KMP算法j1234567891011121413151617k+1Pnext[j]若P8≠P16，且next[8]=4，則有以下關(guān)系：這兩部分重合4這兩部分重合4.4.2KMP算法j1234567891011121413151617k+1Pnext[j]若P8≠P16，且next[8]=4，則有以下關(guān)系：這兩部分重合4這四部分重合4.4.2KMP算法j1234567891011121413151617k+1Pnext[j]若P8≠P16，且next[8]=44若P16=P4，則next[17]=4+1=54.4.2KMP算法j1234567891011121413151617k+1Pnext[j]這兩部分重合4這兩部分重合若P16≠P4，若next[4]=2，則有以下關(guān)系：這兩個(gè)數(shù)重合24.4.2KMP算法j1234567891011121413151617Pnext[j]這兩部分重合4這兩部分重合若P16=P2，則next[17]=2+1=3，否則繼續(xù)取next[2]=1、next[1]=0；遇到0時(shí)還沒有出結(jié)果，則遞推結(jié)束，此時(shí)next[17]=1。這兩個(gè)數(shù)重合24.4.2KMP算法已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進(jìn)行匹配，第一次出現(xiàn)“失配”(s[i]!=t[j])時(shí)，i=j=5，則下次開始匹配時(shí)，i和j的值分別是（）。A.i=1，j=0B.i=5，j=0C.i=5，j=2D.i=6，j=2說明：本題為2015年全國考研題j012345t[j]abaabcnext[j]-100112選C示例4.4.2KMP算法（補(bǔ)充）next數(shù)組的缺陷aaabaaaabisaaajtab01234next4.4.2KMP算法（補(bǔ)充）前面全都是‘a(chǎn)’，卻要一個(gè)一個(gè)全部和‘b’比較一次。aaabaaaabisaaajtab01234next4.4.2KMP算法（補(bǔ)充）為什么會(huì)發(fā)生這種情況呢？abcabxyisabcjtab01112next3cz4.4.2KMP算法（補(bǔ)充）當(dāng)檢測到‘c’和‘x’不同時(shí)，j會(huì)回溯為next[6]=3。此時(shí)t[j]仍為‘c’。已經(jīng)得知‘c’!=‘x’，但仍需要再次判斷后，才能讓j回溯到正確的位置next[3]=1。abcabxyisabcjtab01112next3cz4.4.2KMP算法（補(bǔ)充）發(fā)現(xiàn)t[6]=t[3]時(shí)，直接使next[6]=next[3]=1。next[]數(shù)組的修正值nextval[]：在j++以及k++之后，在向nextval[]數(shù)組中填入數(shù)值時(shí)，如果t[j]==t[k]，直接使next[j]=next[k]即可。abcitabnextval0c11111j4.4.2KMP算法（補(bǔ)充）voidget_nextval(char

*t,intnextval[]){i=1;nextval[1]=0;j=0;while(i<t[0]){if(j==0||t[i]==t[j]){++i;++j;

if(t[i]!=t[j])nextval[i]=j;elsenextval[i]==nextval[j];}elsej=nextval[j];}}voidget_next(char

*t,intnext[]){i=1;j=0;next[1]=0;while(i<t[0]){if(j==0||t[i]==t[j]){++i;++j;next[i]=j;}elsej=next[j];}}4.4.2KMP算法（補(bǔ)充）使用nextval[修正數(shù)組實(shí)現(xiàn)KMP算法時(shí)，不會(huì)出多次無用比較的現(xiàn)象。nextval數(shù)組中nextval[2]不一定等于1，且可能會(huì)有多個(gè)0出現(xiàn)。aaaitabnextval00004jwhile(i<t[0]){if(j==0||t[i]==t[j]){++i;++j;

if(t[i]!=t[j])nextval[i]=j;elsenextval[i]==nextval[j];}elsej=nextval[j];}4.4.2KMP算法（補(bǔ)充）aaaabcdsaaaaitanextval0000j設(shè)主串長度為n，模式串長度為m，求nextval數(shù)組的過程循環(huán)了m-1次，與主串的匹配過程也比較了m次，最好時(shí)間復(fù)雜度為：O(m)。4.4.2KMP算法（補(bǔ)充）2025/8/1181O(m+n)=O([m,2m]+[n,2n])

計(jì)算next數(shù)組的時(shí)間復(fù)雜度+遍歷比較的復(fù)雜度1.當(dāng)前字符匹配時(shí)，同時(shí)移動(dòng)i++，j++；2.當(dāng)前字符不匹配，且j=0時(shí)，只移動(dòng)i++，j=0不動(dòng)；3.當(dāng)前字符不匹配，且j!=0時(shí)，i不變，strM[j]回跳，最多跳j次。但j由前面匹配的情況1確定，而情況1總共不可能出現(xiàn)超過n次，所以總回跳不會(huì)超過n次。最壞情況：i++次數(shù)（情況一+情況二）+j回跳（情況3）=n+最壞n=2n[m,2m]也可以類似證明設(shè)主串s的