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

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

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

1緒論27圖62線性表88動態(tài)存儲管理略3棧和隊列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串的表示和實現(xiàn)4.3串的模式匹配算法26.10.2023數(shù)據(jù)結(jié)構(gòu)4記為：

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

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

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

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

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

——《數(shù)據(jù)結(jié)構(gòu)與算法》中山大學(xué)出版社③空串是哪個串的子串？a是不是自己的子串？26.10.2023數(shù)據(jù)結(jié)構(gòu)7C語言中已有類似串運算函數(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)//

求串長，即返回串S中的元素個數(shù)

Concat(&T,S1,S2)//

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

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

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

求串長：intstrlen(char*s);

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

子串T定位：charstrchr(char*s,char*c);……參考C語言書P135-138注：用C處理字符串時，要調(diào)用標(biāo)準(zhǔn)庫函數(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例如：可利用串比較、求串長和求子串等操作實現(xiàn)定位函數(shù)Index(S,T,pos).算法基本思想：在主串S中取從第i（i=pos）個字符起，取長度和串T相等的子串和串T比較，若相等，則返回值為i否則i++，直到S中不存在和T相等的子串為止。26.10.2023數(shù)據(jù)結(jié)構(gòu)12IntIndex（StringS，StringT，intpos）{//T為非空串，若主串S中第pos個字符之后存在與T相等的子串，

//則返回第一個這樣的子串在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’?。㊣ndex(S,T,pos)//返回子串T在pos之后的位置’IAMAWORKER’26.10.2023數(shù)據(jù)結(jié)構(gòu)14提問：當(dāng)s=’IAMASTUDENT’時,

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

根據(jù)教材P71倒1行的函數(shù)說明，INDEX（s,’A’）返回的只是“第一次”出現(xiàn)的位置。 如果還要搜索后面的A，則pos變量要跟著變才行。也就是說，要把得到的“第一次”位置再代入INDEX（s,’A’，pos）函數(shù)中循環(huán)操作才行。26.10.2023數(shù)據(jù)結(jié)構(gòu)15解：因為SubString(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串的特點：串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集；串的基本操作和線性表差別很大串的基本操作中，通常以“串的整體”作為操作對象。26.10.2023數(shù)據(jù)結(jié)構(gòu)174.2 串的表示和實現(xiàn)定長順序存儲表示——用一組地址連續(xù)的存儲單元存儲串值的字符序列，屬靜態(tài)存儲方式。堆分配存儲表示——用一組地址連續(xù)的存儲單元存儲串值的字符序列,但存儲空間是在程序執(zhí)行過程中動態(tài)分配而得。串的塊鏈存儲表示——鏈?zhǔn)椒绞酱鎯κ紫葟娬{(diào)：串與線性表的運算有所不同，是以“串的整體”作為操作對象，例如查找某子串，在主串某位置上插入一個子串等。串有三種機內(nèi)表示方法：順序存儲鏈?zhǔn)酱鎯?6.10.2023數(shù)據(jù)結(jié)構(gòu)18定長順序存儲特點：用一組連續(xù)的存儲單元來存放串，直接使用定長的字符數(shù)組來定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲分配。例如：#defineMaxstrlen255//用戶可用的最大串長

typedefunsignedcharSString[Maxstrlen＋1]SString;

//P73

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

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

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

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

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

(參見教材P76）此處T.ch[0]沒有用來裝串長，因為另有T.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個字符之前（包括尾部）插入串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串長度}returnOK;}//StrInsert例2：用“堆”方式編寫串插入函數(shù)

(參見教材P75)

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

；法2存儲密度為

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

A

B

C

I

NULLheadheadABCD

EFGH

I###NULL

串值所占的存儲位置存儲密度=

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

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

charch[CHUNKSIZE];

//每個結(jié)點中的數(shù)據(jù)域

structChunk*next;//每個結(jié)點中的指針域}Chunk;塊鏈類型定義：塊鏈函數(shù)的編寫略typedefstruct{//其次定義用鏈?zhǔn)酱鎯Φ拇愋?/p>

Chunk*head;//頭指針

Chunk*tail;//尾指針

intcurLen;//結(jié)點個數(shù)

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

BF算法

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

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

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

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

利用演示系統(tǒng)看BF算法執(zhí)行過程。BF算法設(shè)計思想：將主串S的第pos個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串S的下一字符（pos+1）起，重新與T第一個字符比較。直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值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é)束，說明匹配成功

elsereturn0;}//Index例2：

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

（參見教材P79）相當(dāng)于子串向右滑動一個字符位置匹配成功后指針仍要回溯！因為要返回的是被匹配的首個字符位置。ijS=‘a(chǎn)babc

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

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

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

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

KMP算法的推導(dǎo)過程③KMP算法的實現(xiàn)（關(guān)鍵技術(shù):計算next[j]）④KMP算法的時間復(fù)雜度全書一大亮點！26.10.2023數(shù)據(jù)結(jié)構(gòu)30奇妙的結(jié)果：k僅與模式串T有關(guān)?、贙MP算法的推導(dǎo)過程：（見教材P81）請抓住部分匹配時的兩個特征：兩式聯(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是追求的新起點加速的前提：T首與Tj處有相同子串注意：j為當(dāng)前已知的失配位置，我們的目標(biāo)是計算新起點k。式中僅剩一個未知數(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(已知)，可以歸納出計算新起點

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

k

|1<k<j

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

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

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

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

j

]＝max{

k

|1<k<j

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

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

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

next[j]怎么計算？怎樣計算模式T所有可能的失配點j

所對應(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時max{k|1<k<j且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1

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

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

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

j=4時,k={2，3}，要查看‘T1’=‘T3’及‘T1T2’=‘T2T3’是否成立j=5時,k={2，3，4}，要查看‘T1’=‘T4’，‘T1T2’=‘T3T4’和‘T1T2T3’=‘T2T3T4’以此類推，可得后續(xù)next[j]值?？捎醚菔境绦蝌炞Cnext[j]與s無關(guān)，可以預(yù)先計算例：26.10.2023數(shù)據(jù)結(jié)構(gòu)35下一個要討論的問題是：如何用遞推方式來求出最大相同子串的長度呢？換言之，如何讓電腦替我們求出最大相同子串呢？這個問題一旦解決，整個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ū)別：遞推：由“小”到“大”遞進；遞歸：由“大”到“小”嵌套。遞歸法（第1章自測卷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所有可能的失配點j所對應(yīng)的next[j]計算出來；第二步：執(zhí)行定位函數(shù)Index_kmp（與BF算法模塊非常相似）③KMP算法的實現(xiàn)—即Index()操作的實現(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];}

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

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

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

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

i:123456789

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

T：aaaabj：12345

next[j]：01234先計算next[j]：此時效率不高的原因為：子串前4位相同時，主串字符若與其中一個不相等，則不必再與其余3個比較。而實際上還在依次比較。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ù)的改進算法見教材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é)束，說明匹配成功

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

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