第4章 串（String）教學(xué)課件

數(shù)據(jù)結(jié)構(gòu)26.10.2023數(shù)據(jù)結(jié)構(gòu)2內(nèi)容安排章內(nèi)容學(xué)時(shí)

章內(nèi)容學(xué)時(shí)

1緒論27圖62線性表88動(dòng)態(tài)存儲(chǔ)管理略3棧和隊(duì)列49查找44串310內(nèi)部排序85數(shù)組和廣義表311外部排序26樹和二叉樹1012文件略26.10.2023數(shù)據(jù)結(jié)構(gòu)3第4章串（String）4.1串類型的定義4.2串的表示和實(shí)現(xiàn)4.3串的模式匹配算法26.10.2023數(shù)據(jù)結(jié)構(gòu)4記為：

s=‘a(chǎn)1a2……..an’(n≥0)

串名串值（用‘’括起來(lái)）串即字符串，是由零個(gè)或多個(gè)字符組成的有限序列，是數(shù)據(jù)元素為單個(gè)字符的特殊線性表。4.1串類型的定義隱含結(jié)束符‘\0’，即ASCII碼NULL為何要單獨(dú)討論“串”類型？1）字符串操作比其他數(shù)據(jù)類型更復(fù)雜（如拷貝、連接操作）2）程序設(shè)計(jì)中，處理對(duì)象很多都是串類型。26.10.2023數(shù)據(jù)結(jié)構(gòu)5若干術(shù)語(yǔ)：串長(zhǎng)：串中字符的個(gè)數(shù)（n≥0）.n=0時(shí)稱為空串

?？瞻状河梢粋€(gè)或多個(gè)空格符組成的串。問(wèn)：空串和空白串有無(wú)區(qū)別？答：有區(qū)別。空串(NullString)是指長(zhǎng)度為零的串；而空白串(BlankString),是指包含一個(gè)或多個(gè)空白字符‘

’(空格鍵)的字符串.26.10.2023數(shù)據(jù)結(jié)構(gòu)6

子串：子串位置：字符位置：串相等：例1：現(xiàn)有以下4個(gè)字符串：a=‘BEI’ b=‘JING’c=‘BEIJING’d=‘BEIJING’問(wèn)：①他們各自的長(zhǎng)度？a是c和d的子串，在c和d中的位置都是1串S中任意個(gè)連續(xù)的字符序列叫S的子串;S叫主串。子串的第一個(gè)字符在主串中的序號(hào)。字符在串中的序號(hào)。串長(zhǎng)度相等，且對(duì)應(yīng)位置上字符相等。②a是哪個(gè)串的子串？在主串中的位置是多少？a=3，b=4，c=7，d=8“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串稱為S的真子串?！?/p>

——《數(shù)據(jù)結(jié)構(gòu)與算法》中山大學(xué)出版社③空串是哪個(gè)串的子串？a是不是自己的子串？26.10.2023數(shù)據(jù)結(jié)構(gòu)7C語(yǔ)言中已有類似串運(yùn)算函數(shù)！ADTString{Objects:

D={ai

|ai∈CharacterSet,i=1,2,…，n,n≥0}Relations:

R1={<ai-1,ai>|ai-1,ai∈D,i=2,…，n}functions:

//至少有13種基本操作

StrAssign(&T,chars)//

串賦值，生成值為chars的串T StrCompare(S,T)//

串比較，若S>T，返回值大于0…StrLength(S)//

求串長(zhǎng)，即返回串S中的元素個(gè)數(shù)

Concat(&T,S1,S2)//

串連接，用T返回S1＋S2的新串

SubString(&Sub,S,pos,len)//

求S中pos起長(zhǎng)度為len的子串

StrCopy（&T,S）//由串S復(fù)制得到T ……

Index(S,T,pos)

//子串定位函數(shù)（模式匹配），返回位置

Replace(&S,T,V)//用子串V替換子串T

}ADTString串的抽象數(shù)據(jù)類型定義（參見教材P71）最小操作子集26.10.2023數(shù)據(jù)結(jié)構(gòu)8StrCopy(&T,S)初始條件：串S已經(jīng)存在操作結(jié)果：由串S復(fù)制得到串TConcat（&T，S1，S2）初始條件：串S1和S2存在操作結(jié)果：用T返回有S1和S2連接而成地新串。StrLength(S)初始條件：串S已經(jīng)存在操作結(jié)果：返回S的元素個(gè)數(shù)，即串的長(zhǎng)度StrCompare（S，T）初始條件：串S和串T存在操作結(jié)果：若S>T,返回值>0

若S=T,返回值=0

若S<T,返回值<026.10.2023數(shù)據(jù)結(jié)構(gòu)9SubString（&Sub,pos,len）初始條件：串S存在，1=<pos=<StrLength(s)

且0=<len=<StrLength(s)-pos+1操作結(jié)果：用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串。Index（S，T，pos）初始條件：串S存在，T是非空，1=<pos=<StrLength(s)操作結(jié)果：若主串S中存在和串T值相同的子串，則返回子串在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置，否則函數(shù)值為0。Replace(&S,T,V)初始條件：串S，T和V存在，T是非空串；操作結(jié)果：用V替換主串S中出現(xiàn)的所有與T相等的不重疊的子串。這些操作不可能利用其它串操作來(lái)實(shí)現(xiàn)，即最小操作子集26.10.2023數(shù)據(jù)結(jié)構(gòu)10注：Concat操作＝concatenation，把多個(gè)短字符串合并為長(zhǎng)字符串復(fù)習(xí)：C語(yǔ)言中常用的串運(yùn)算C串比較：intstrcmp(char*s1,char*s2);

求串長(zhǎng)：intstrlen(char*s);

串連接：charstrcat(char*to,char*from)

子串T定位：charstrchr(char*s,char*c);……參考C語(yǔ)言書P135-138注：用C處理字符串時(shí)，要調(diào)用標(biāo)準(zhǔn)庫(kù)函數(shù)#include<string.h>

類CStrCompare(S,T)StrLength(S)Concat(&T,S1,S2)Index(S,T,pos)26.10.2023數(shù)據(jù)結(jié)構(gòu)11例如：可利用串比較、求串長(zhǎng)和求子串等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos).算法基本思想：在主串S中取從第i（i=pos）個(gè)字符起，取長(zhǎng)度和串T相等的子串和串T比較，若相等，則返回值為i否則i++，直到S中不存在和T相等的子串為止。26.10.2023數(shù)據(jù)結(jié)構(gòu)12IntIndex（StringS，StringT，intpos）{//T為非空串，若主串S中第pos個(gè)字符之后存在與T相等的子串，

//則返回第一個(gè)這樣的子串在S中的位置，否則返回0；if（pos>0）{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;}//while}//if}//Index()StrCompare（SubString（S，i，StrLength（T）），T）=？0subsubSnmmi=posn-m+1subiTTT26.10.2023數(shù)據(jù)結(jié)構(gòu)13Replace(&S,T,V)

//用子串V替換子串T

設(shè)s

=’IAMASTUDENT’,t

=’GOOD’,q=’WORKER’。求：例1：StrLength(s)＝

StrLength(t)＝

SubString(&sub,s,8,7)=SubString(&sub,t,2,1)=Index(s,‘A’)=Index(s,t

)=Replace(&s,‘STUDENT’,q

)=14//參見P714‘STUDENT’‘O’30

（s中沒有t=’GOOD’！）Index(S,T,pos)//返回子串T在pos之后的位置’IAMAWORKER’26.10.2023數(shù)據(jù)結(jié)構(gòu)14提問(wèn)：當(dāng)s=’IAMASTUDENT’時(shí),

INDEX（s,’A’，pos）=3，若想搜索后面那個(gè)‘A’怎么辦？答:

根據(jù)教材P71倒1行的函數(shù)說(shuō)明，INDEX（s,’A’）返回的只是“第一次”出現(xiàn)的位置。 如果還要搜索后面的A，則pos變量要跟著變才行。也就是說(shuō)，要把得到的“第一次”位置再代入INDEX（s,’A’，pos）函數(shù)中循環(huán)操作才行。26.10.2023數(shù)據(jù)結(jié)構(gòu)15解：因?yàn)镾ubString(s,6,2)＝‘A’；SubString(s,7,8)＝‘STUDENT’Concat(,t,SubString(s,7,8))＝’GOODSTUDENT’所以：Concat(,SubString(s,6,2),Concat(t,SubString(s,7,8)))＝‘AGOODSTUDENT’例2：設(shè)s

=’IAMASTUDENT’,t

=’GOOD’,求：

Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))＝？26.10.2023數(shù)據(jù)結(jié)構(gòu)16串的特點(diǎn)：串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集；串的基本操作和線性表差別很大串的基本操作中，通常以“串的整體”作為操作對(duì)象。26.10.2023數(shù)據(jù)結(jié)構(gòu)174.2 串的表示和實(shí)現(xiàn)定長(zhǎng)順序存儲(chǔ)表示——用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，屬靜態(tài)存儲(chǔ)方式。堆分配存儲(chǔ)表示——用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列,但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。串的塊鏈存儲(chǔ)表示——鏈?zhǔn)椒绞酱鎯?chǔ)首先強(qiáng)調(diào)：串與線性表的運(yùn)算有所不同，是以“串的整體”作為操作對(duì)象，例如查找某子串，在主串某位置上插入一個(gè)子串等。串有三種機(jī)內(nèi)表示方法：順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)26.10.2023數(shù)據(jù)結(jié)構(gòu)18定長(zhǎng)順序存儲(chǔ)特點(diǎn)：用一組連續(xù)的存儲(chǔ)單元來(lái)存放串，直接使用定長(zhǎng)的字符數(shù)組來(lái)定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲(chǔ)分配。例如：#defineMaxstrlen255//用戶可用的最大串長(zhǎng)

typedefunsignedcharSString[Maxstrlen＋1]SString;

//P73

SStrings;//s是一個(gè)可容納255個(gè)字符的順序串。注：一般用SString[0]來(lái)存放串長(zhǎng)信息（如pascal語(yǔ)言）；C語(yǔ)言約定在串尾加結(jié)束符‘\0’，以利操作加速，但不計(jì)入串長(zhǎng)（用首址和串長(zhǎng)、或首址和尾標(biāo)記來(lái)描述串?dāng)?shù)組）若字符串超過(guò)Maxstrlen則自動(dòng)截?cái)啵ㄒ驗(yàn)殪o態(tài)數(shù)組存不進(jìn)去）。

26.10.2023數(shù)據(jù)結(jié)構(gòu)19例：用順序存儲(chǔ)方式編寫求子串函數(shù)SubString(&Sub,S,pos,len)

Status

SubString(SString&sub,SStringS,intpos,intlen){if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)returnERROR;//若pos和len參數(shù)越界，則告警

Sub[1……len]=S[pos……pos+len-1];Sub[0]=len;returnOK;}將串S中從第pos個(gè)字符開始、長(zhǎng)度為len的字符序列復(fù)制到串Sub中。（注：考慮到函數(shù)的通用性，應(yīng)當(dāng)讓串Sub的預(yù)留長(zhǎng)度與S一樣）子串長(zhǎng)度s=‘a(chǎn)1a2……..an’poslenSub[]討論：想存放超長(zhǎng)字符串怎么辦？改用動(dòng)態(tài)分配的一維數(shù)組——堆26.10.2023數(shù)據(jù)結(jié)構(gòu)20思路：利用malloc函數(shù)合理預(yù)設(shè)串長(zhǎng)空間。特點(diǎn)：

若在操作中串值改變，還可以利用realloc函數(shù)按新串長(zhǎng)度增加空間（即動(dòng)態(tài)數(shù)組概念）。Typedefstruct{char*ch;

//若非空串,按串長(zhǎng)分配空間;否則ch=NULLintlength;//串長(zhǎng)度}HString堆分配存儲(chǔ)特點(diǎn)：仍用一組連續(xù)的存儲(chǔ)單元來(lái)存放串，但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。堆T的存儲(chǔ)結(jié)構(gòu)描述：T.chT.length26.10.2023數(shù)據(jù)結(jié)構(gòu)21C是指針變量，可以自增！意即每次后移一個(gè)數(shù)據(jù)單元。直到終值為“假”停止，串尾特征是c＝‘\0’＝NULL＝0StatusStrAssign(HString&T,char*chars){//生成一個(gè)串T,T值←串常量charsif(T.ch)free(T.ch);//釋放T原有空間

for(i=0,c=chars;c;++i,++c);//求chars的串長(zhǎng)度i例1：編寫建堆函數(shù)

(參見教材P76）此處T.ch[0]沒有用來(lái)裝串長(zhǎng)，因?yàn)榱碛蠺.length分量if(!i){T.ch=NULL;T.length=0;} else{ if(!(T.ch=(char*)malloc(i*sizeof(char)))) exit(OVERFLOW);

T.ch[0..i-1]=chars[0..i-1]; T.length=i; } ReturnOK;}//StrAssign26.10.2023數(shù)據(jù)結(jié)構(gòu)22StatusStrInsert(HString&S,intpos,HStringT){

//在串S的第pos個(gè)字符之前（包括尾部）插入串Tif(pos<1||pos>S.length+1)returnERROR;//pos不合法則告警

if(T.length){

//只要串T不空，就需要重新分配S空間，以便插入Tif(!（S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))exit(OVERFLOW);//若開不了新空間，則退出

for(i=S.length-1;i>=pos-1;--i)S.ch[i+T.length]=S.ch[i];

//為插入T而騰出pos之后的位置，即從S的pos位置起全部字符均后移

S.ch[pos-1…pos+T.length-2]=T.ch[0…T.length-1];//插入T，略/0

S.length+=T.length;//刷新S串長(zhǎng)度}returnOK;}//StrInsert例2：用“堆”方式編寫串插入函數(shù)

(參見教材P75)

1≤pos≤S.length+126.10.2023數(shù)據(jù)結(jié)構(gòu)23討論：法1存儲(chǔ)密度為

；法2存儲(chǔ)密度為

；顯然，若數(shù)據(jù)元素很多，用法2存儲(chǔ)更優(yōu)—稱為塊鏈結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)特點(diǎn)：用鏈表存儲(chǔ)串值，易插入和刪除。法1：鏈表結(jié)點(diǎn)的數(shù)據(jù)分量長(zhǎng)度取1（個(gè)字符）法2：鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取n(例如n=4)1/29/15=3/5

A

B

C

I

NULLheadheadABCD

EFGH

I###NULL

串值所占的存儲(chǔ)位置存儲(chǔ)密度=

實(shí)際分配的存儲(chǔ)位26.10.2023數(shù)據(jù)結(jié)構(gòu)24對(duì)塊鏈表的整體描述#defineCHUNKSIZE80

//每塊大小，可由用戶定義typedefstructChunk{//首先定義結(jié)點(diǎn)類型

charch[CHUNKSIZE];

//每個(gè)結(jié)點(diǎn)中的數(shù)據(jù)域

structChunk*next;//每個(gè)結(jié)點(diǎn)中的指針域}Chunk;塊鏈類型定義：塊鏈函數(shù)的編寫略typedefstruct{//其次定義用鏈?zhǔn)酱鎯?chǔ)的串類型

Chunk*head;//頭指針

Chunk*tail;//尾指針

intcurLen;//結(jié)點(diǎn)個(gè)數(shù)

}Lstring;//串類型只用一次，前面可以不加Lstring對(duì)每個(gè)結(jié)點(diǎn)的描述26.10.2023數(shù)據(jù)結(jié)構(gòu)25算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）4.3串的模式匹配算法

BF算法

（又稱古典的、經(jīng)典的、樸素的、窮舉的）

KMP算法算法種類：帶回溯，速度慢避免回溯，匹配速度快，是全課程的亮點(diǎn)之一定位問(wèn)題稱為串的模式匹配(PatternMatching)，即子串定位運(yùn)算，它是串處理系統(tǒng)中最重要的操作之一。典型函數(shù)為Index(S,T,pos)，見教材P7126.10.2023數(shù)據(jù)結(jié)構(gòu)26BF算法的實(shí)現(xiàn)—即編寫Index(S,T,pos)函數(shù)例1：

S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，pos=1，

求：串T在串S中第pos個(gè)字符之后的位置。

利用演示系統(tǒng)看BF算法執(zhí)行過(guò)程。BF算法設(shè)計(jì)思想：將主串S的第pos個(gè)字符和模式T的第1個(gè)字符比較，若相等，繼續(xù)逐個(gè)比較后續(xù)字符；若不等，從主串S的下一字符（pos+1）起，重新與T第一個(gè)字符比較。直到主串S的一個(gè)連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個(gè)字符的序號(hào)，即匹配成功。否則，匹配失敗，返回值0.26.10.2023數(shù)據(jù)結(jié)構(gòu)27IntIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){++i,++j}

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

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

//指針回溯到下一首位，重新開始匹配

}if(j>T[0])returni-T[0];

//子串結(jié)束，說(shuō)明匹配成功

elsereturn0;}//Index例2：

S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，求Index(S,T,5)

（參見教材P79）相當(dāng)于子串向右滑動(dòng)一個(gè)字符位置匹配成功后指針仍要回溯！因?yàn)橐祷氐氖潜黄ヅ涞氖讉€(gè)字符位置。ijS=‘a(chǎn)babc

abcacbab’T=‘a(chǎn)bcac’pos=526.10.2023數(shù)據(jù)結(jié)構(gòu)28討論：若n為主串長(zhǎng)度，m為子串長(zhǎng)度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m＝O(n*m)一般的情況是：O(n+m)

推導(dǎo)方法：要從最好到最壞情況統(tǒng)計(jì)總的比較次數(shù)，然后取平均。BF算法的時(shí)間復(fù)雜度最好的情況是：一配就中！只比較了m次。能否利用已部分匹配過(guò)的信息而加快模式串的滑動(dòng)速度？能！而且主串S的指針i不必回溯！最壞情況也能達(dá)到O(n+m)請(qǐng)看KMP算法！最惡劣情況是：主串前面n-m個(gè)位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！所以總次數(shù)為：(n-m)*m+m

＝(n-m+1)*m26.10.2023數(shù)據(jù)結(jié)構(gòu)29KMP算法（特點(diǎn)：速度快）①

KMP算法設(shè)計(jì)思想②

KMP算法的推導(dǎo)過(guò)程③KMP算法的實(shí)現(xiàn)（關(guān)鍵技術(shù):計(jì)算next[j]）④KMP算法的時(shí)間復(fù)雜度全書一大亮點(diǎn)！26.10.2023數(shù)據(jù)結(jié)構(gòu)30奇妙的結(jié)果：k僅與模式串T有關(guān)?、贙MP算法的推導(dǎo)過(guò)程：（見教材P81）請(qǐng)抓住部分匹配時(shí)的兩個(gè)特征：兩式聯(lián)立可得：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’S=‘a(chǎn)babc

a

b

cacbab’T=‘a(chǎn)

b

cac’ik則T的k-1～1位＝S前i-1～i-(k-1)位

即(4-2）式含義設(shè)目前打算與T的第k字符開始比較(1)(2)‘T1…Tk-1’則T的j-1～j-(k-1)位＝

S前i-1～i-(k-1)位

即(4-3）式含義ikjS=‘a(chǎn)babc

a

bcacbab’T=‘a(chǎn)b

cac’剛才肯定是在S的i處和T的第j字符處失配‘Tj-(k-1)…Tj-1’截取一段，但k有限制，1<k<jk是追求的新起點(diǎn)加速的前提：T首與Tj處有相同子串注意：j為當(dāng)前已知的失配位置，我們的目標(biāo)是計(jì)算新起點(diǎn)k。式中僅剩一個(gè)未知數(shù)k，理論上已可解！26.10.2023數(shù)據(jù)結(jié)構(gòu)31根據(jù)模式串T的規(guī)律：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’由當(dāng)前失配位置j(已知)，可以歸納出計(jì)算新起點(diǎn)

k的表達(dá)式。next[j]＝0當(dāng)j＝1時(shí)//不比較max{

k

|1<k<j

且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況討論：（1）next[j]的物理意義是什么？（2）next[j]具體怎么求？—即KMP算法的實(shí)現(xiàn)令k=

next[j]（k與j顯然具有函數(shù)關(guān)系），則取T首與Tj處最大的相同子串新起點(diǎn)

k怎么求？26.10.2023數(shù)據(jù)結(jié)構(gòu)32（1）

next[j]有何物理意義？next[j]函數(shù)表征著模式T中最大相同前綴子串和后綴子串（真子串）的長(zhǎng)度?？梢?，模式中相似部分越多，則next[j]函數(shù)越大，它既表示模式T字符之間的相關(guān)度越高，也表示j位置以前與主串部分匹配的字符數(shù)越多。即：next[j]越大，模式串向右滑動(dòng)得越遠(yuǎn)，與主串進(jìn)行比較的次數(shù)越少，時(shí)間復(fù)雜度就越低（時(shí)間效率）。next[

j

]＝max{

k

|1<k<j

且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’

}模式串從第1位往右直到K-1位模式串從j的前一位往左經(jīng)過(guò)K-1位想一想：如果主串和模式均為二進(jìn)制碼流，用KMP算法效果如何？T=‘a(chǎn)baabcac’再想一想：如果主串是外存中一個(gè)大文件，用KMP算法效果又如何？（2）next[j]具體怎么求？—即KMP算法的實(shí)現(xiàn)26.10.2023數(shù)據(jù)結(jié)構(gòu)33計(jì)算Next[j]的方法：

當(dāng)j=1時(shí)，Next[j]=0；//Next[j]=0表示根本不進(jìn)行字符比較當(dāng)j>1時(shí)，Next[j]的值為：模式串的位置從1到j(luò)-1構(gòu)成的串中所出現(xiàn)的首尾相同的子串的最大長(zhǎng)度加1。無(wú)首尾相同的子串時(shí)Next[j]的值為1。//Next[j]=1表示從模式串頭部開始進(jìn)行字符比較（2）

next[j]怎么計(jì)算？怎樣計(jì)算模式T所有可能的失配點(diǎn)j

所對(duì)應(yīng)的

next[j]？26.10.2023數(shù)據(jù)結(jié)構(gòu)34從兩頭往中間比較

模式串T：abaabcac

可能失配位j：12345678新匹配位k=next[j]:next[j]＝0

當(dāng)j＝1時(shí)max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1

其他情況01122312討論：j=1時(shí),next[j]≡

0；//屬于“j=1”情況;j=2時(shí),next[j]≡

1；//找不到1<k<j的k，屬于“其他情況”；剛才已歸納：j=3時(shí),k={2}，只需查看‘T1’=‘T2’成立否，No則屬于其他情況

j=4時(shí),k={2，3}，要查看‘T1’=‘T3’及‘T1T2’=‘T2T3’是否成立j=5時(shí),k={2，3，4}，要查看‘T1’=‘T4’，‘T1T2’=‘T3T4’和‘T1T2T3’=‘T2T3T4’以此類推，可得后續(xù)next[j]值。可用演示程序驗(yàn)證next[j]與s無(wú)關(guān)，可以預(yù)先計(jì)算例：26.10.2023數(shù)據(jù)結(jié)構(gòu)35下一個(gè)要討論的問(wèn)題是：如何用遞推方式來(lái)求出最大相同子串的長(zhǎng)度呢？換言之，如何讓電腦替我們求出最大相同子串呢？這個(gè)問(wèn)題一旦解決，整個(gè)KMP算法就可以掌握得很透徹了。voidget_next(SStringT,int&next[]){//

//求模式串T的next函數(shù)值并存入數(shù)組next[]。i=1;next[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];}}//get_next遞推法編程，參見教材P83程序26.10.2023數(shù)據(jù)結(jié)構(gòu)36求解next[j]流程圖（遞推）

i=1;j=0next[1]=0i<T[0]j==0||T[i]==T[j]++i;++j;next[i]=j;j=next[j];ENDYYNN26.10.2023數(shù)據(jù)結(jié)構(gòu)37注：遞歸與遞推的區(qū)別：遞推：由“小”到“大”遞進(jìn)；遞歸：由“大”到“小”嵌套。遞歸法（第1章自測(cè)卷4.2題）：longintfact(n)intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}遞推法：fact=1;for(i=1;i<=n;i++)fact*=i;例如：求f(n)=n!26.10.2023數(shù)據(jù)結(jié)構(gòu)38第一步，先把模式T所有可能的失配點(diǎn)j所對(duì)應(yīng)的next[j]計(jì)算出來(lái)；第二步：執(zhí)行定位函數(shù)Index_kmp（與BF算法模塊非常相似）③KMP算法的實(shí)現(xiàn)—即Index()操作的實(shí)現(xiàn)IntIndex_KMP(SStringS,SStringT,intpos){//見教材P82

i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i,++j}//不失配則繼續(xù)比較后續(xù)字符

else{j=next[j];}

//特點(diǎn)：S的i指針不回溯，而且從T的k位置開始匹配

}if(j>T[0])returni-T[0];

//子串結(jié)束，說(shuō)明匹配成功

elsereturn0;}//Index_KMP26.10.2023數(shù)據(jù)結(jié)構(gòu)39前面定義的next函數(shù)在某些情況下還是有缺陷的，例如模式aaaab與主串a(chǎn)aabaaaab匹配時(shí)的情況：S:aaabaaaabT:aaaab

i:123456789

aaaabaaaabaaaab討論：next[j]是否完美無(wú)缺？先用演示程序驗(yàn)證似乎慢了一點(diǎn)？能否再提速？由此派生出next函數(shù)的改進(jìn)算法

T：aaaabj：12345

next[j]：01234先計(jì)算next[j]：此時(shí)效率不高的原因?yàn)椋鹤哟?位相同時(shí)，主串字符若與其中一個(gè)不相等，則不必再與其余3個(gè)比較。而實(shí)際上還在依次比較。aaaab26.10.2023數(shù)據(jù)結(jié)構(gòu)40voidget_nextval(SStringT,int&nextval[]){

//next函數(shù)修正值存入數(shù)組nextvali=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;else

nextval[i]=nextval[j];}elsej=nextval[j];}}//get_nextvalnext函數(shù)的改進(jìn)算法見教材P84算法4.8，稱為nextval[j]26.10.2023數(shù)據(jù)結(jié)構(gòu)41IntIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){++i,++j}

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

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

//指針回溯到下一首位，重新開始匹配

}if(j>T[0])returni-T[0];

//子串結(jié)束，說(shuō)明匹配成功

elsereturn0;}//Index例2：S=‘a(chǎn)babcabcacbab’，T=‘a(chǎn)bcac’，求Index(S,T,5)

（參見教材P79）相當(dāng)于子串向右滑動(dòng)一個(gè)字符位置匹配成功后指針仍要回溯！因?yàn)橐祷氐氖潜黄ヅ涞氖讉€(gè)字符位置。ijS=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’pos=526.10.2023數(shù)據(jù)結(jié)構(gòu)42第一步，先把模式T所有可能的失配點(diǎn)j所對(duì)應(yīng)的next[j]計(jì)算出來(lái)；第二步：執(zhí)行定位函數(shù)Index_kmp（與BF算法模塊非常相似）③KMP算法的實(shí)現(xiàn)—即