第四章 字符串

4.1字符串的類型定義4.2字符串的表示和實(shí)現(xiàn)4.2.1串的順序存儲(chǔ)結(jié)構(gòu)4.2.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4.3字符串的模式匹配4.4字符串的應(yīng)用舉例第四章字符串定義和概念字符串簡稱為串（String）:由零個(gè)或多個(gè)字符組成的有限序列。記為：s=’a1a2…an’（n≥0）概念：s為串名‘a(chǎn)1a2…an’為串值例如：s=‘YantaiUniversity’n為串的長度ai

為串中字符，以ASCII形式存儲(chǔ)n=0，空串（NullString），記為：Ф若ai

=‘’，則稱為空格串(blankstring)字符串的抽象數(shù)據(jù)類型定義ADTSTRING{數(shù)據(jù)對(duì)象：D={ai

|ai

CharacterSet

，i=1，2，...，n，n>=0}

數(shù)據(jù)關(guān)系：R={<ai-1

，ai>|ai-1，ai

D，i=2,...,n}基本操作:串賦值：StringAssign(S,T)串復(fù)制:StringCopy(S,T)

求串長：StringLenth(S)

串判等：StringEqual(S,T)

串聯(lián)接：StringConcat(S,T)

求子串：SubString(S,start,length)

初始條件：串s存在，1<=start<=Stringlength(s)+1,

且：0<=length<=Stringlength(s)-start+1

操作結(jié)果：返回主串s中以start為起始位置、長度等于length的子串}STRING這6個(gè)操作是串類型的最小操作子集子串的定義：串中任意連續(xù)的字符組成的子序列稱為該串的子串Length可以為0，此時(shí)表示求的是空串。以S＝’abcdefghij’為例，length=10,如果start=11,則這時(shí)就是求空串。若start=6,則0<=length<=10-6+1=5,及此時(shí)的length的最大值為5，從第6個(gè)字符開始到結(jié)束總共有5個(gè)字符字符串的抽象數(shù)據(jù)類型定義（續(xù)）子串定位：Index(S,T)（S是主串，T是模式串）擴(kuò)展形式為：Index(S,T,pos)（pos=1時(shí)就是上述形式）初始條件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)操作結(jié)果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置，否則函數(shù)值為0字符串的抽象數(shù)據(jù)類型定義（續(xù)）置換：Replace(S,T,V)

插入子串：StringInsert(S,start,T)

初始條件：串S和T存在，1<=start<=

Stringlength(s)+1

操作結(jié)果：在串S的第start個(gè)字符之前插入串T。刪除子串：StringDelete(S,start,length)

初始條件：串S和T存在，1<=start<=

Stringlength(s)-length+1

操作結(jié)果：從串S中刪除第start個(gè)字符起長度為length的子串。

長度分別為18、7、3、3；且b、c、d都是a的子串；b在a中的位置是1，c在a中的位置是12；c和d兩串相等

例：a=’WelcometoBeijing’b=’Welcome’c=’Bei’d=’Bei’

表明可以插入在串S的最后串和線性表的比較串的邏輯結(jié)構(gòu)和線性表極為相似，即都有位序的問題。區(qū)別僅在于串的數(shù)據(jù)對(duì)象約束為字符集。然而：串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以“單個(gè)元素”作為操作對(duì)象，如：在線性表中查找某個(gè)元素、求取每個(gè)元素、在某個(gè)位置上插入、刪除一個(gè)元素等；而在串的基本操作中，通常以“串的整體”作為操作對(duì)象，如：在串中查找某個(gè)子串、求取一個(gè)子串、在串的某個(gè)位置上插入一個(gè)子串以及刪除一個(gè)子串等。關(guān)于串的操作對(duì)于串的基本操作集可以有不同的定義方法，讀者在使用高級(jí)程序設(shè)計(jì)語言中的串類型時(shí)，應(yīng)以該語言的參考手冊(cè)為準(zhǔn)。如在C語言中串賦值StrAssign、串復(fù)制StrCopy、串比較StrCompare、求串長StrLength、串聯(lián)接StrConcat、求子串SubString等6種操作構(gòu)成串類型的最小操作子集。即這些操作不可能利用其他串操作來實(shí)現(xiàn)。反之，其他串操作（除串清除ClearString和串銷毀DestroyString外）均可在這個(gè)最小操作子集上實(shí)現(xiàn)。C語言中的串操作函數(shù)gets(string)輸入一個(gè)字符串；puts(string)輸出一個(gè)字符串；strcat(str1,str2)將兩個(gè)串連接成一個(gè)新串strcpy(str1,str2)將字符串str2的值復(fù)制給str1變量strcmp(str1,str2)將兩個(gè)字符串進(jìn)行比較strlen(str)求字符串的長度strlwr(str)將字符串str中的大寫字母換成小寫字母strupr(str)將字符串str中的小寫字母換成大寫字母定位函數(shù)Index(S,T,pos)例如可利用串比較、求串長和求子串等操作實(shí)現(xiàn)定位函數(shù)Index(S,T,pos)。算法的基本思想為：在主串S中取從第i（i的初值為pos）個(gè)字符起、長度和串T相等的子串和T比較，若相等，則求得函數(shù)值為i，否則i值增1直至串S中不存在和串T相等的子串為止。定位函數(shù)Index(S,T,pos)Strcompare(Substring(S,i,StrLength(T)),T)=0?可用下列算法實(shí)現(xiàn)int

Index(String

S,String

T,intpos){//T為非空串，若主串S中第pos個(gè)字符之后存在與T相等的子串，則返回第一個(gè)這樣的子串在S中的位置，否則返回0if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;

while(i<=n-m+1)//當(dāng)i加上T的長度超過串S的長度時(shí)結(jié)束

{StringAssign(sub，SubString(S，i，m));∥在串s中從第i個(gè)字符開始取長度為m的字串

if(StrCompare(sub,T)!=0)++i;elsereturni;}//while}//ifreturn0;//S中不存在與T相等的子串}//Index教材P.68.算法4.1串的表示和實(shí)現(xiàn)如果在程序設(shè)計(jì)語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲(chǔ)此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)，因此字符串也有存儲(chǔ)映像的問題。串的表示和實(shí)現(xiàn)串有三種機(jī)內(nèi)表示方法串的順序存儲(chǔ)結(jié)構(gòu):用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)串中的字符序列。

1.定長順序存儲(chǔ)表示：事先定義字符串的最大長度2.“堆”分配存儲(chǔ)表示：在程序執(zhí)行過程中，利用標(biāo)準(zhǔn)函數(shù)malloc和free動(dòng)態(tài)地分配或釋放存儲(chǔ)字符串的存儲(chǔ)單元，并以一個(gè)特殊的字符（例如’\0’）作為字符串的結(jié)束標(biāo)志鏈?zhǔn)奖硎?.塊鏈存儲(chǔ)表示靜態(tài)的動(dòng)態(tài)的串的順序存儲(chǔ)結(jié)構(gòu)定長順序存儲(chǔ)表示:事先定義字符串的最大長度#defineMAX_STRING255∥用戶可能達(dá)到的最大串長typedefunsignedcharSString[MAX_STRING+1];∥0號(hào)單元存放串的長度,字符從1號(hào)單元開始存放串的實(shí)際長度可在這個(gè)預(yù)定義長度的范圍內(nèi)隨意設(shè)定，超過預(yù)定義長度的串值則被舍去。稱之為“截?cái)唷痹O(shè)有兩個(gè)字符串，分別為：‘data’和‘structures’，且假設(shè)strlen=10，則strconcat(‘data’，‘structures’）＝‘datastruct’而strconcat(‘structures’,’data’)＝‘structures’因此：串的聯(lián)接算法中需分三種情況考慮：1).兩串長度之和小于等于字符串最大長度：未截?cái)啵?).兩串長度之和大于字符串最大長度：截?cái)啵?).第一字符串的長度大于字符串最大長度：截?cái)?，僅取第一字符串綜上所述：對(duì)于定長順序存儲(chǔ)表示的字符串進(jìn)行串的運(yùn)算時(shí)，其基本操作為：‘字符序列的復(fù)制’串的順序存儲(chǔ)結(jié)構(gòu)之“堆”分配存儲(chǔ)表示“堆”分配存儲(chǔ)表示：在程序執(zhí)行過程中，利用標(biāo)準(zhǔn)函數(shù)malloc和free動(dòng)態(tài)地分配或釋放存儲(chǔ)字符串的存儲(chǔ)單元，并以一個(gè)特殊的字符（例如’\0’）作為字符串的結(jié)束標(biāo)志.稱串值共享的存儲(chǔ)空間為“堆”typedef

struct{char*str;//若是非空串，則按串長分配存儲(chǔ)區(qū)，否則str為NULL

intlength;//串長度}HString;注意由于在字符串操作中通常以“串的整體”作為操作對(duì)象,所以雖然是用malloc動(dòng)態(tài)的分配存儲(chǔ),但是因?yàn)榇鎯?chǔ)地址是連續(xù)的，也把它認(rèn)為是順序存儲(chǔ)的。實(shí)際上，此處的str是一個(gè)字符串指針通常，C語言中通過的串類型就是以這種存儲(chǔ)方式實(shí)現(xiàn)的，系統(tǒng)利用函數(shù)malloc()和free()進(jìn)行串值空間的動(dòng)態(tài)管理，為每一個(gè)新產(chǎn)生的串分配一個(gè)存儲(chǔ)區(qū)，稱串值共享的存儲(chǔ)空間為“堆”，C語言的串以一個(gè)空字符‘\0’為結(jié)束符，串長是一個(gè)隱含值。這類串操作的實(shí)現(xiàn)算法為：先為新生成的串分配一個(gè)存儲(chǔ)空間，然后進(jìn)行串值的復(fù)制?；静僮?串的賦值int

StringAssign(HString*S,HString*T){∥將串T的值賦給串Sif(S->str)free(S->str);∥若s已經(jīng)存在，將它占據(jù)的空間釋放掉

len=T->length;∥T串的長度

S->length=len;∥賦予字符串長度

if(!len)∥空串

{S->str=(char*)malloc(sizeof(char));S->str[0]=’\0’;//串結(jié)束標(biāo)志，‘\0’是人為的加上去的

}else∥非空串

{S->str=(char*)malloc((len+1)*sizeof(char));∥分配空間

if(!S->str)returnERROR;for(i=0;i<=len;i++)∥對(duì)應(yīng)的字符賦值

S->str[i]=T->str[i];}∥ifreturnOK;}∥StringAssign

上述第二種方式定義下串不可以整體賦值，需要每個(gè)字符實(shí)現(xiàn)復(fù)制多余的1個(gè)存放‘\0’教材P.69.算法4.2

基本操作:串聯(lián)接int

StringConcat(HString*S,HString

*T){∥將串T聯(lián)接到串S后

HStringtemp;

StringAssign(&temp,S);∥將S原來的內(nèi)容保留在temp中

S->length=S->length+T->length;∥計(jì)算S和T的長度之和為S的新長度

free(S->str);∥釋放S原來占據(jù)的空間

S->str=(char*)malloc((s->len+1)*sizeof(char));∥重新為S分配空間

if(!s->str)returnERROR;else{∥連接兩個(gè)串的內(nèi)容

for(i=0;i<temp.length;i++)∥將temp的值先賦給SS->str[i]=temp.str[i];for(j=0;j<=T->length;j++,i++)∥將T的值賦在S現(xiàn)有值之后

S->str[i]=T->str[j];

free(temp.str);∥釋放為臨時(shí)串temp分配的空間

returnOK;}∥if}∥StringConcat

注意一個(gè)是<,一個(gè)是<=,為什么？即第二個(gè)for把串T的最后一個(gè)‘\0’也復(fù)制過去了。因?yàn)閠emp是一個(gè)變量，所以用temp.length，而S是指針變量，所以用S->str[i]教材P.70.算法4.3int

Index(HString*S,HString*T){∥返回子串T在主串S中的位置，若T非S的子串返回0i=0;j=0;∥設(shè)置兩個(gè)掃描指針

while(i<S->length&&j<T->length){if(S->str[i]==T->str[j]){i++;j++;}else∥對(duì)應(yīng)字符不相等時(shí)，重新比較

{i=i-j+1;j=0;}∥if}∥whileif(j==T->length)returni-T->length+1;∥返回子串在主串中的位置

elsereturn0;}∥Index

基本操作的算法:子串定位注意第二種順序存儲(chǔ)表示時(shí)從0號(hào)開始存放教材P.70.算法4.4定長順序表示中的C表示方法在C中，字符串的概念是：以‘\0’為結(jié)尾的字符數(shù)組。初始化：Strings;S[0]=‘\0’;串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)串作為一種特殊的線性表（數(shù)據(jù)元素為字符），使用順序表示時(shí)，做插入和刪除運(yùn)算，運(yùn)算量很大，不方便。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：string

^S直接使用線性鏈表來存儲(chǔ)字符串：效率太低實(shí)際分配的存儲(chǔ)單元串值所占的存儲(chǔ)單元存儲(chǔ)密度=

串的塊鏈存儲(chǔ)結(jié)構(gòu)#defineCHUNKSIZE80∥可由用戶定義的塊大小typedef

struct

Chunknode{∥結(jié)點(diǎn)結(jié)構(gòu)

charch[CHUNKSIZE];//每個(gè)結(jié)點(diǎn)放一個(gè)串，如文本的一行

struct

Chunknode*next;}Chunk;typedef

struct

{∥串的鏈表結(jié)構(gòu)

Chunk*head,*tail;∥串的頭和尾指針

int

curlen;∥串的當(dāng)前長度

}LString;

Sstring####^塊鏈?zhǔn)浇Y(jié)構(gòu)的定義注意教材P.71.的結(jié)點(diǎn)定義錯(cuò)誤塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是存儲(chǔ)密度高,缺點(diǎn)是做插入/刪除等操作時(shí)可能會(huì)引起結(jié)點(diǎn)之間字符的移動(dòng),算法實(shí)現(xiàn)比較復(fù)雜這種結(jié)構(gòu)下處理文本時(shí)，每行是一個(gè)結(jié)點(diǎn)，行與行之間用指針相連接關(guān)于串的塊鏈存儲(chǔ)結(jié)構(gòu)串值也可以用鏈表來存儲(chǔ)，由于串的數(shù)據(jù)元素是一個(gè)字符，它只有8位二進(jìn)制數(shù)，因此用鏈表存儲(chǔ)時(shí)，通常一個(gè)結(jié)點(diǎn)中存放的不是一個(gè)字符，而是一個(gè)子串，例如，在文本編輯系統(tǒng)中，整個(gè)文本編輯區(qū)可以看成是一個(gè)串，每一行是一個(gè)子串，構(gòu)成一個(gè)結(jié)點(diǎn)。即同一行的串用定長結(jié)構(gòu)（80個(gè)字符），行和行之間用指針相聯(lián)接。文本編輯時(shí)插入或刪除一行很方便，不影響別的行。塊鏈運(yùn)算：插入Hesi

sdenuta##.t?Heisastudent.Heisabrightstudent.串鏈表結(jié)構(gòu)的尾指針串鏈表結(jié)構(gòu)的頭指針curlen串鏈表結(jié)構(gòu)的頭結(jié)點(diǎn)塊鏈運(yùn)算：插入Hesi

bgenira##.t?httus

d#####尾指針不變curlen練習(xí)題：選擇若串S=’software’,其子串的數(shù)目是（）。【西安電子科技大學(xué)2001應(yīng)用一、2（2分）】A．8B．37C．36D．9答案為：B實(shí)際上為：8＋7＋6＋5＋4＋3＋2＋1＋1＝37即是取1個(gè)字符的組合、取2個(gè)字符的組合、……一直到取8個(gè)字符的組合（串本身可以認(rèn)為是其自身的字串），還包括空串也是子串。選擇設(shè)S為一個(gè)長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個(gè)數(shù)為（）?！局锌圃河?jì)算所1997】A．2n-1B．n2

C．(n2/2)+(n/2)D．(n2/2)+(n/2)-1E.(n2/2)-(n/2)-1F.其他情況答案為：D此題出的比前一道題好，無有關(guān)子串的二義性問題選擇串的長度是指（）【北京工商大學(xué)2001一、6（3分）】A．串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)答案為：B填空串是一種特殊的線性表，其特殊性表現(xiàn)在__(1)__；串的兩種最基本的存儲(chǔ)方式是__(2)__、__(3)__；兩個(gè)串相等的充分必要條件是__(4)__?！局袊V業(yè)大學(xué)2000一、3（4分）】（1）：其數(shù)據(jù)元素都是字符（2）：順序存儲(chǔ)（3）：鏈?zhǔn)酱鎯?chǔ)（4）：串的長度相等且兩串中對(duì)應(yīng)位置的字符也相等4.3字符串的模式匹配（子串定位）這是串的一種重要操作，很多軟件，若有“編輯”菜單項(xiàng)的話，則其中必有“查找”子菜單項(xiàng)。4.3字符串的模式匹配（子串定位）首先回憶一下串匹配（查找）的定義：Index(S,T,pos)（S是主串，T是模式串）初始條件：串S和T存在，T是非空串，

1≤pos≤StrLength(S)操作結(jié)果：若主串S中存在和串T值相同的子串，則返回它在主串S中第pos個(gè)字符之后第一次出現(xiàn)的位置，否則函數(shù)值為0。4.3字符串的模式匹配（子串定位）方法1：樸素的模式匹配算法（簡單算法）（Brute-Force算法即BF算法）；方法2：首尾模式匹配算法；方法3：KMP算法；以下的討論采用定長順序存儲(chǔ)結(jié)構(gòu)#defineMAX_STRING255∥用戶可能達(dá)到的最大串長typedefunsignedcharSString[MAX_STRING+1];∥0號(hào)單元存放串的長度,字符從1號(hào)單元開始存放樸素的串的模式匹配子串定位算法Index基本思想：先以主串S中第一個(gè)字符為S子串的頭一個(gè)字符，截取模式串T的長度的子串，然后與模式串T中的字符逐個(gè)比較，若子串與模式串相同，即返回S子串的頭一個(gè)字符位置作為查找的位置；否則，取S中第二個(gè)字符為子串頭，將其往后的字符再依次與模式串T比較判斷是否相等，以此類推直到找到位置或未有一個(gè)子串與模式串相同為止。

樸素的模式匹配主串S=’ababcabcacbab’，模式串T=‘a(chǎn)bcac’

↓i=3第一趟匹配：ababcabcacbab

abc↑j=3↓i=2第二趟匹配：ababcabcacbab

a↑j=1

↓i=7第三趟匹配：ababcabcacbab

abcac↑j=5

↓i=4第四趟匹配：ababcabcacbab

a↑j=1

↓i=5第五趟匹配：ababcabcacbab

a↑j=1

↓i=11第六趟匹配：ababcabcacbab

abcac↑j=6該算法存在著指針的“回溯”，回溯次數(shù)越多，效率越低。如：S=000000000000001T=00001算法的時(shí)間復(fù)雜度為O(n*m)樸素的模式匹配算法int

Index(SStringS,T){∥返回子串T在主串S中的位置，若T非S的子串返回0i=1;j=1;∥設(shè)置兩個(gè)掃描指針

while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){i++;j++;}//繼續(xù)比較后續(xù)字符

else∥對(duì)應(yīng)字符不相等時(shí)，指針后退重新開始匹配

{i=i-j+2;

j=1;}∥if}∥whileif(j>T[0])returni-T[0];∥返回子串在主串中的位置

elsereturn0;}∥Index

i=8S=‘dfnamrujhzasnamruot’T=‘namruo’j=6改進(jìn)算法之：首尾模式匹配算法基本思想：

先比較模式串的第一個(gè)字符，

再比較模式串的最后一個(gè)字符，

最后比較模式串中從第二個(gè)到第n－1個(gè)字符。

改進(jìn)算法之：首尾模式匹配算法基本思想：先比較模式串的第一個(gè)字符，再比較模式串的最后一個(gè)字符，最后比較模式串中從第二個(gè)到第n-1個(gè)字符。

主串:ababcabcaaabcbaabc模式串:aa(2次)

aaa(1+2次)aaabcba(2+5次)aaaa(2+2次)aa(2次)abcba(5次)例如主串S=’ababcabcaaabcbaabc’，模式串T為’abcba’

當(dāng)首尾相等時(shí)，從模式串的第2個(gè)字符起依次第3個(gè)第4個(gè)，……，一直比較到模式串的倒數(shù)第2個(gè)為止首尾模式匹配算法int

Index_FL(SStringS,T){∥返回子串T在主串S中的位置。若不存在，則函數(shù)值

//為0。其中，T非空。

sLength=S[0];

tLength=T[0];i=1;

patStartChar=T[1];//模式串的第一個(gè)字符

patEndChar=T[tLength];∥模式串的最后一個(gè)字符

首尾模式匹配算法（續(xù)）while(i<=sLength–tLength+1)

{if(S[i]!=patStartChar)++i;∥重新查找匹配起始點(diǎn)

elseif(S[i+tLength-1]!=patEndChar)++i;∥模式串的“尾字符”不匹配，重新查找匹配起始點(diǎn)

else{

∥檢查從第2個(gè)字符起的中間字符的匹配情況

k=1;j=2;while(j<tLength&&S[i+k]==T->str[j]){++k;++j;}∥while

if(j==tLength)returni;

else++i;

∥重新開始下一次的匹配檢測

}∥else

}∥whilereturn0;}∥Index_FL首尾模式匹配算法減少了一定量的比較，但是并未真正的消除回溯當(dāng)首尾相等時(shí)，從模式串的第2個(gè)字符起依次第3個(gè)第4個(gè)，……，一直比較到模式串的倒數(shù)第2個(gè)為止改進(jìn)方法之：KMP算法特點(diǎn)

無需回溯在O（n＋m）的時(shí)間量級(jí)上完成串的模式匹配操作

三個(gè)人的名字：D.K.KnuthV.R.PrattJ.H.Morris1.KMP算法

s=‘a(chǎn)bbaba’t=‘a(chǎn)ba’

∵t1=s1,t2=s2,t3≠s3又∵t1≠t2∴t1≠s2∴t右移一位后與s2（及b）的比較一定不等又∵

t1=t3∴

t1≠s3

∴t再右移一位后與s3（及b）的比較一定不等

因此：把t直接右移三位，及t1和s4直接比較即可。相對(duì)于s而言，消除了回溯。1.KMP算法(續(xù)）問題

substr(t,1,j-1)=substr(s,i-j+1,i-1)

tj

≠

si

時(shí)，確定t中哪個(gè)字符和si進(jìn)行比較。把該字符記為tk，顯然k<j.

對(duì)于不同的j，k值也不同。Knuth等人發(fā)現(xiàn)：此k值僅依賴于模式串t本身前j個(gè)字符的構(gòu)成，而與s無關(guān)。用next[j]表示與j對(duì)應(yīng)的k值。1.KMP算法(續(xù)）若next[j]>0:則tj

≠

si則用tk

＝tnext[j]與si比較若next[j]＝0:則tj

≠

si則用si＋1與t1比較Ex：S=‘a(chǎn)cabaabaabcacaabc’T=‘a(chǎn)baabc’next值：j123456模式串a(chǎn)baabcnext[j]011223Next[j]的意義是：

↓i=2第一趟匹配：主串a(chǎn)cabaabaabcacaabc

模式串a(chǎn)b↑j=2next[2]=1↓i=2第二趟匹配：主串a(chǎn)cabaabaabcacaabc

模式串a(chǎn)↑j=1next[1]=0

↓i=3→

↓i=8第三趟匹配：主串a(chǎn)cabaabaabcacaabc

模式串a(chǎn)baabc↑j=1→

↑j=6next[6]=3↓i=8→

↓i=12第四趟匹配：主串a(chǎn)cabaabaabcacaabc

模式串(ab)

aabc

↑j=3→

↑j=7

1.KMP算法(續(xù)）j123456模式串a(chǎn)baabcnext[j]0112231.KMP算法(續(xù)）int

Index_KMP(SStringS,T){//利用模式串T的next函數(shù)求T在主串S中的位置的KMP算法。

//其中，T非空

i=1;j=1;//初始化

while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i;++j;}∥繼續(xù)比較后繼字符

elsej=next[j];

∥模式串向右移動(dòng)

}∥whileif(j>T[0])returni-T[0];∥匹配成功

elsereturn0;}∥Index_KMP

該算法的時(shí)間復(fù)雜度為O(n),n為主串s的長度請(qǐng)把該算法與樸素的模式匹配算法進(jìn)行比較，觀察相同和不同之處。差別僅在粉紅色部分教材P.73.算法4.5略有不同2.如何求next[j]主串：模式串：當(dāng)Si

≠Pj時(shí)，Si應(yīng)與Pk（k<j)繼續(xù)比較，此時(shí)必定有：（1）2.如何求next[j]（續(xù)）已經(jīng)得到的“部分匹配”結(jié)果是：

（2）由（1）式和（2）式可得：（3）2.如何求next[j]（續(xù)）該（3）式說明：k的取值應(yīng)使的k-1個(gè)字符組成的子串相等。即：substr(p,1,k-1)=substr(p,j-k+1,k-1)P右移j-k位后：?2.如何求next[j]（續(xù)）可能有兩種情況：1）：若pk=pj，則表明即：next[j+1]=k+1，也就是說：next[j+1]=next[j]+12）：若pk<>pj，則求next函數(shù)值的問題又是一個(gè)模式匹配的問題，只不過整個(gè)模式串既是主串又是模式串。2.如何求next[j]（續(xù)）例：S=’abaabdabaabc’P=‘a(chǎn)baabc’i=6j=6s6≠p6,此時(shí)應(yīng)該s6與p3比較，則：i＝6，j＝6，即k=3∴j123456模式串a(chǎn)baabcnext[j]0112232.如何求next[j]（續(xù)）令next[j]=k,則next[j]表明：當(dāng)si

≠tj時(shí)，在模式串t中需重新和主串中si

繼續(xù)進(jìn)行比較的字符的位置。所以next函數(shù)的定義如下：即集合為空時(shí)，即不存在一個(gè)滿足：2.如何求next[j]（續(xù)）j12345678模式串tabaabcacnext[j]

例如：01122312如何求next[j]（續(xù)）

next數(shù)組的具體生成方法：

next數(shù)組的值完全取決于模式串t本身，而與目標(biāo)主串無關(guān)，所以首先求出next數(shù)組的值：2.如何求next[j]（續(xù)）

next數(shù)組的具體生成方法：實(shí)際上：求next函數(shù)值的運(yùn)算實(shí)質(zhì)上也是一個(gè)模式匹配的問題。若表明在第j＋1個(gè)字符之前不存在長度為next[j]+1的和首字符起的子串模式相匹配的子串，然而是否有可能一個(gè)長度較短的可與首字符起的子串模式相匹配的子串呢？由kmp算法的啟發(fā)：設(shè)next[j]=k’,則應(yīng)將和相比較，若則說明在模式的第j+1個(gè)字符之前存在一個(gè)長度為next[k]+1且與首字符起的子串模式相匹配的子串。否則依次類推找更短的子串，直至不存在可匹配的子串，則next[j+1]=1。2.如何求next[j]（續(xù)）

next數(shù)組的具體生成方法：如下圖的模式中，已求得前6個(gè)字符的next函數(shù)值，現(xiàn)在求next[7]。∵next[6]=3,又∵則需比較

和（∵next[3]=1),這相當(dāng)于將子串模式向右滑動(dòng)?！摺鄋ext[7]=1;∵則next[8]=next[7]＋1＝2

j123456

7

8模式串tabaabc

a

cnext[j]011223

1

22.如何求next[j]（續(xù)）

next數(shù)組的具體生成方法：求next函數(shù)值的過程是一個(gè)遞推過程，分析如下：

已知：next[1]=0;

假設(shè)：next[j]=k，又T[j]=T[k]

則：

next[j+1]=k+1

若：

T[j]≠T[k]

則需往前回溯，檢查T[j]=T[?]

這實(shí)際上也是一個(gè)匹配的過程，不同在于：主串和模式串是同一個(gè)串。2.如何求next[j]（續(xù)）求next數(shù)組的算法voidGet_Next(SStringT,intnext[]){//求模式串T的next函數(shù)值存入next數(shù)組中

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];//j指針回溯

}//while}//Get_Next該算法的時(shí)間復(fù)雜度為O(m)。通常：模式串的長度m比主串的長度n要小很多，即：m<<n,所以增加這點(diǎn)時(shí)間是值得的Kmp算法的時(shí)間復(fù)雜度為O(m+n)與教材P.74.算法4.6略有不同2.如何求next[j]（續(xù)）注意：滿足（3）式的k可能有多個(gè)，此時(shí)應(yīng)該選擇其中最大的k，因?yàn)檫@樣移動(dòng)的次數(shù)（j－k）最少。以P=‘a(chǎn)aab’為例：當(dāng)P4=b匹配不成功時(shí)，按照式（3），k可以取1、2或3（分別對(duì)應(yīng)于右移3位、2位或1位），但只有取

k＝3時(shí)，即右移j-k=4-3=1位時(shí)，才能保證不丟失任何匹配成功時(shí)的可能。2.如何求next[j]（續(xù)）K=3,p右移一位：aaab

匹配成功

K=2,p右移二位：aaab

匹配不成功

K=1,p右移三位：aaab

匹配不成功此例中，p1p2=p2p3第四章練習(xí)已知串S=‘a(chǎn)aab’,其Next數(shù)組值為（）?！疚靼搽娮涌萍即髮W(xué)1996一、7（2分）】A．0123B．1123C．1231D．1211答案為：A串‘a(chǎn)babaaababaa’的next數(shù)組為（）?！局猩酱髮W(xué)1999一、7】A．012345678999B．012121111212C．011234223456D．012301232234答案為：C模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為________?！疚靼搽娮涌萍即髮W(xué)2001軟件一、6（2分）】答案為：01122312模式串t=‘a(chǎn)bcaabbcabcaabdab’，該模式串的next數(shù)組的值為（）A．01112211123456712B．01112121123456112C．01110013101100701D．01112231123456712E．01100111011001701F．01102131011021701【北京郵電大學(xué)1998二、3（2分）】答案為：D設(shè)字符串S=‘a(chǎn)abaabaabaac'，P=‘a(chǎn)abaac'（1）給出S和P的next值和nextval值；（2）若S作主串，P作模式串，試給出利用BF算法和KMP算法的匹配過程?！颈狈浇煌ù髮W(xué)1998二（15分）】

S的next值為：012123456789P的next值為：012123改進(jìn)的求next數(shù)組的算法事實(shí)上，上述的求next數(shù)組的算法有缺陷。如：S=‘a(chǎn)aabaaaab’T=‘a(chǎn)aaab’此時(shí)next數(shù)組的值為：則根據(jù)kmp算法，還需進(jìn)行共三次比較。實(shí)際上因?yàn)閠中的所以不需要再和s4進(jìn)行比較，而可以將模式串一氣向右滑動(dòng)4個(gè)字符位置直接進(jìn)行的比較，也就是說：若next[j]=k,而又有不需要再和tk進(jìn)行比較，而直接和進(jìn)行比較即可。換句話說：此時(shí)的

next[j]=next[k]j1

2

34

5模式串taaaabnext[j]012343.改進(jìn)的求next數(shù)組的算法(續(xù)）voidGet_NextVal(SStringT,int

nextval[]){//求模式串T的next函數(shù)修正值存入nextval數(shù)組中

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];}//if

elsej=nextval[j];}//while}//Get_NextVal與教材P.74.算法4.7略有不同3.改進(jìn)的求next數(shù)組的算法(續(xù)）j模式串tnext[j]nextval[j]

12345aaaab

01234

00004關(guān)于串的匹配算法主要有四個(gè)：簡單算法；KMP算法；NEXT函數(shù)值的求法；NEXTVAL函數(shù)值的求法；

這四個(gè)算法是相同的，當(dāng)然有些區(qū)別。只要記住一個(gè)算法，其它算法就好理解了，當(dāng)然要弄清楚NEXT函數(shù)值的意義字符串的應(yīng)用文本編輯p.74.大致了解第四章總結(jié)1.

熟悉串的七種基本操作的定義，并能夠利用這些基本操作來實(shí)現(xiàn)串的其它各種操作的方法；2.熟練掌握在串的定長順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法；3.掌握串的堆存儲(chǔ)結(jié)構(gòu)以及在其上實(shí)現(xiàn)串操作的基本方法；4.理解串匹配的KMP算法，熟悉NEXT函數(shù)的定義，學(xué)會(huì)手工計(jì)算給定模式串的NEXT函數(shù)值和NEXTVAL函數(shù)值；5.理解串操作的應(yīng)用方法；作業(yè)第四章4.1,4.2,4.4,4.5,4.6,4.9,4.104.12,4.14應(yīng)用題試?yán)肒MP算法和改進(jìn)算法分別求p1=‘a(chǎn)baabaa’和p2=‘a(chǎn)abbaab’的next函數(shù)和nextval函數(shù)?！緰|南大學(xué)1999一、6（8分）】P1的next：0112234P1的nextval：0102102P2的next：0121123P1的nextval：0021002選擇字符串‘a(chǎn)babaabab’的nextval

為（）A．(0,1,0,1,0,4,1,0,1)B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1)D．(0,1,0,1,0,1,0,1,1)答案為：ANext數(shù)組值為：011234234填空字符串’ababaaab’的nextval函數(shù)值為________。【北京郵電大學(xué)2001二、4（2分）】答案為：Nextval值為：01010421Next值為：01123422選擇模式串t=‘a(chǎn)bcaabbcabcaabdab’，該模式串的next數(shù)組的值為（），nextval數(shù)組的值為（）。A．01112211123456712B．01112121123456112C．01110013101100701D．01112231123456712E．01100111011001701F．01102131011021701【北京郵電大學(xué)1998二、3（2分）】Next值為：DNextval值為：F應(yīng)用題KMP算法(字符串匹配算法)較Brute(樸素的字符串匹配)算法有哪些改進(jìn)?【大連海事大學(xué)1996三、1((2分)】KMP算法的主要優(yōu)點(diǎn)是主串指針不回溯。當(dāng)主串很大、不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時(shí)，KMP算法的優(yōu)點(diǎn)就更為突出。應(yīng)用題已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值?！颈本┼]電大學(xué)1997三（10分）】模式串的next函數(shù)定義Next值為：011122312345Nextval值為：011021301105給出字符串‘a(chǎn)bacabaaad’在KMP算法中的next和nextval數(shù)組?！颈本┼]電大學(xué)2000三、1（5分）】

Next：

0112123422Nextval：0102010422令t=‘a(chǎn)bcabaa’,求其next函數(shù)值和nextva