數(shù)據(jù)結(jié)構(gòu)-用C語言描述（第二版） -寧正元 第4章 串文檔閱讀

第第四四章章串串串的基本概念串的存儲實(shí)現(xiàn)串的模式匹配算法漢字串第4章

串第四章

串教材其余課件及動畫素材請查閱在線教務(wù)輔導(dǎo)網(wǎng)在線教務(wù)輔導(dǎo)網(wǎng)：

QQ:349134187

或者直接輸入下面地址：

第四章

串串又稱字符串，是一種特殊的線性表，是數(shù)據(jù)元素類型為字符的線性表，其應(yīng)用非常廣泛，是許多軟件系統(tǒng)（如字符編輯、情報檢索、詞法分析、符號處里、自然語言翻譯等系統(tǒng)）的操作對象。本章介紹串的概念和各種存儲結(jié)構(gòu)，并討論串的聯(lián)接、求子串、串的插入、刪除和置換以及串的模式匹配等運(yùn)算。第4章

串第四章

串4.1串的基本概念串是由n個(n≥0)字符組成的有限序列，一般記作：S=“a1a2…an”其中，S是串名，用成對的雙引號括起來的字符序列是串的值，ai可以是字母，數(shù)字或其它字符；n為串中字符的個數(shù)，稱為串的長度，長度為零的串稱為空串。需要注意的是，成對的雙引號本身僅作為標(biāo)記，不屬于串。例如，串“Beijing”和“Beijing”的長度分別是7和8。空串和空格串是兩個不同的情況，例如，S1=“”即為空串，它的長度為0，空串內(nèi)無任何字符，而S2=“”為空格串，即由一個或多個空格組成，其長度為串中空格的個數(shù)，空格符可以出現(xiàn)在字符序列的任意部位。串中任意個連續(xù)的字符組成的子序列稱為子串，一個串可以包含若干個子串，相應(yīng)地，包含子串的串稱為主串。字符在串中的序號稱作該字符在串中的位置。當(dāng)兩個串長度相等且對應(yīng)字符都相同時相等。第四章

串串的邏輯結(jié)構(gòu)與線性表的區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。串結(jié)構(gòu)的形式化定義為：String=(D，R)其中，D={ai︱ai∈character，i=1，2…n，n≥0}，R={<a

i-1

ai>︱a

i-1∈D，i=1，2，…n

}串的基本運(yùn)算有：初始化ClearString（s）：初始化串s。StrAssign（s，ch）：串賦值。StrCopy(s，t)：串復(fù)制。StrConcat（t，s1，s2）：串聯(lián)接。求串長StrLen（s）：返回s串的元素個數(shù)，即s串的長度。串比較StrCom（s，t）求子串SubStr（t，s，pos，len）：返回s串的第pos個字符起始的長度為len的子串。插入運(yùn)算StrInsert（s，pos，t）：把串t的值插入到串s的第pos個字符之后。刪除運(yùn)算StrDel（s，pos，len）：將串s中從第pos字符起始的長度為len的子串刪除。第四章

串子串定位StrIndex（s，t，pos）：從主串s的第pos個字符起定位串s中是否存在和串t值相等的子串，若存在，則返回子串t在主串s中第一次出現(xiàn)的位置，否則，返回函數(shù)值0。例如，StrIndex（“Beijing”，“jin”，1）=4；StrIndex（“Beijing”，“jng”，2）=0置換運(yùn)算StrReplace（s，pos，len,t）：用t串置換s串中第pos字符開始的連續(xù)的len個字符。例如，s=“Thatфisфaфbag！”，則

StrReplace（s，3，2，“is”）＝“Thisфisфaфbag！”有時用另一種置換運(yùn)算StrReplace（s，t，v）表示用v串置換所有在s串中出現(xiàn)的與t串相等的子串。例如，s=“if（j<n）ф

j＋＋；”，t=“j”，v=“i”，則

StrReplace（s，t，v）=“if（i<n）ф

i＋＋；”以上介紹的是有關(guān)串的一些基本運(yùn)算，利用它們可以處理關(guān)于串的各種操作，在使用高級程序設(shè)計語言中的串類型時，對于串的基本運(yùn)算可以有不同的定義方法。第四章

串4.2.1串的定長順序存儲及運(yùn)算實(shí)現(xiàn)1.串的定長順序存儲串的順序存儲結(jié)構(gòu)簡稱順序串，是把串中的字符依次存放在一組地址連續(xù)的存儲單元中。有時將為字符串分配一個固定長度的一組地址連續(xù)的存儲單元的存儲分配方法稱之為定長順序存儲分配。定長順序存儲分配的實(shí)現(xiàn)，要結(jié)合具體的計算機(jī)編址方式進(jìn)行，通常有三種實(shí)現(xiàn)方式：（1）緊縮方式緊縮方式將串長顯式地直接存儲，字符依次順序放在連續(xù)的幾個單元中，這種存儲方式的優(yōu)點(diǎn)是充分地利用了空間，然而運(yùn)算不太方便。假定計算機(jī)按字編址，若串S為“DataФStructure”，‘Ф’表示空格字符，則S串有14個字符，存儲S串的長度14和每個字符，一共需占用4個存儲單元，如圖4.1所示。4.2串的存儲實(shí)現(xiàn)第四章

串非緊縮方式非緊縮方式是每個單元只存放一個字符，串的長度不顯式存儲，由串中字符占存儲單元的數(shù)目來隱式確定。如圖4.2給出了上述串的非緊縮存儲。顯然，非緊縮存儲方式對于串運(yùn)算比較方便，但存儲空間沒有得到有效的利用。單字節(jié)存儲方式計算機(jī)按字節(jié)編址，每個字節(jié)存放一個字符，這時的串長度由串占用的字節(jié)數(shù)隱式確定，如圖4.3所示。這種存儲方式既不浪費(fèi)空間，又使串中每個字符與唯一的地址對應(yīng)，方便了運(yùn)算，對于按字節(jié)編址的計算機(jī)而言是非常合適的。第四章

串第四章

串在C語言中，按字節(jié)尋址。C語言中的串有字符串常量和字符串變量兩種。用雙引號括起來的字符序列為字符串常量，可以用宏定義#define來定義字符串常量的標(biāo)識符。例如，#define

CITY

Beijing對字符串變量而言，C語言將其類型說明為字符型一維數(shù)組。例如，char

ch[100]；其中，數(shù)組ch是一個一維數(shù)組，這里的字符串的最大長度是由其變量說明時決定并且固定不變。通常，在字符串的最后一個字符的后面存放一個結(jié)束標(biāo)志‘\0’。為了更好地討論字符串的運(yùn)算，可將順序串類型定義如下：#define

MAXLEN

81typedef

struct

string{

char

ch[MAXLEN]；int

len；}SeqString；第四章

串2.定長順序串的基本運(yùn)算實(shí)現(xiàn)求串長int

StrLen

(SeqString

*s){

return((*s).len);}串的聯(lián)接兩個串的聯(lián)接就是將一個串緊接著存放在另一個串的后面而得到一個新串。第四章

串void

StrConcat

(SeqString

*t

，

SeqString

*s1，

SeqString

*s2){

int

i，j;if

((*s1).len+(*s2).len<=MAXLEN){for(i=0；i<

(*s1).len

；i++)(*t).ch[i]=(*s1).ch[i];for(j=0；j<

(*s2).len

；j++)(*t).ch[(*s1).len

+j]=(*s2).ch[j];(*t).len=(*s1).len+(*s2).len;}elseif

((*s1).len

<MAXLEN){

for(i=0；i<

(*s1).len

；i++)(*t).ch[i]=(*s1).ch[i];for(j=0；j<

MAXLEN-

(*s1).len；j++)(*t).ch[(*s1).len

+j]=(*s2).ch[j];(*t).len=

MAXLEN；}elseprintf

(“overflow！\n”);}第四章

串（3）求子串void

SubString（t，s，pos，len）/*用t返回主串s中第pos個字符起，長度為len的子串*/SeqString

*t，*s；int

pos，len；{int

i；if((pos<1)||(pos>(*s).len)||(len<0)||(len>(*s).len-pos+1))printf(“pos或len超界\n”);else{

for(i=0；i<

len；i++)(*t).ch[i]=(*s).ch[pos-1+i](*t).len=len;}}第四章

串（4）子串的插入void

StrInsert

(SeqString

*s，

int

pos，

SeqString

*t)/*在串s中的pos位置插入子串t

*/{

int

i；if

((pos<1)

||

(pos>

(*s).len+1))printf(“Insertionpositionincorrect!\n”)；elseif

((*s).len+(*t).len<=MAXLEN){

for

(i=(*s).len-1；i>=pos；i--)(*s).ch[i+(*t).len]=(*s).ch[i];for

(i=0；i<(*t).len；i++)(*s).ch[i+pos]=(*t).ch[i];(*s).len=(*s).len+(*t).len；}else

printf(“overflow！”)；}第四章

串（5）子串的刪除void

StrDel

(s，pos，len)/*從串s中刪除第pos字符起始的長度為len的子串*/SeqString

*s；int

pos，len;{

int

i，j，k；char

*p，*q；if

((pos<1)

||

(pos>

(*s).len))printf(“Deleted

position

incorrect!\n”)；elseif(pos==len)

(*s).len=0；/*刪除整個串*/else第四章

串if

(pos+len-1<=(*s).len

){

i=pos+len-1；j=pos-1；p=&(*s).ch[i]；q=&(*s).ch[j]；k＝len；while（k>0）/*將被刪除位置后的字符向前移動*/{

*q=*p；++p；++q；k--；}*q=*p;(*s).len=(*s).len-len；}elseprintf(“no

characteds

deleted!\n”)；/*沒有l(wèi)en個字符可刪除*/}第四章

串（6）串的置換void

StrReplace(s，t，v)/*用v串替代s串中所有的t子串*/SeqString

*s，*t，*v；{

int

start，pos，m，n，q；n=(*s).len；m=(*t).len；q=(*v).len；

pos=1；do{start=StrIndex(s，t，pos)；/*定位函數(shù)*/if(start!=0){

StrDel

(s，start，m)；StrInsert(s，v，start)；pos=

start+q；(*s).len=(*s).len+q-m；n=(*s).len；}}while

((pos<=n-m+1)

&&

(start

!=0))；}/*StrReplace*/其中，函數(shù)StrIndex()用于從主串s的第pos個字符起定位串s中是否存在和串t值相等的子串，若存在，則返回子串t在主串s中第一次出現(xiàn)的位置，否則，返回函數(shù)值0，第四章

串4.2.2串的堆式動態(tài)存儲及運(yùn)算實(shí)現(xiàn)在許多實(shí)際應(yīng)用的串處理系統(tǒng)中采用堆式動態(tài)存儲分配策略。例如，可以用一維數(shù)組heapchar

heap[MAXLEN]表示堆空間，如圖4.4所示。每當(dāng)產(chǎn)生一個串時，應(yīng)用程序就在執(zhí)行過程中動態(tài)地從free指示的位置為新串值分配一個長度與串長相同的存儲空間，并相應(yīng)修改free的值，同時建立該串的一個描述（稱為符號表），指示串的長度和該串在heap中的第一個字符位置，借助它們在堆結(jié)構(gòu)的串名與串值之間建立起一個對應(yīng)關(guān)系，稱作串名的存儲映像。所有的串名存儲映像就構(gòu)成了一個為系統(tǒng)中所有串名和串值之間建立一一對應(yīng)關(guān)系的映像表（或符號表）。圖4.5是一個堆串存儲及映像表的示例。在C語言中可以直接利用堆來實(shí)現(xiàn)堆串，堆串可定義如下：typedef

struct

/*定義串為結(jié)構(gòu)體*/{

char

*st;

/*串在堆中的開始位置*/int

length;

/*串長度*/}HeapString；第四章

串第四章

串在堆式動態(tài)存儲分配下的串的幾種常見運(yùn)算的實(shí)現(xiàn)。（1）串賦值StrAssign(t，chars)int

StrAssign(HeapString

*t，char

*chars){int

len，i=0;

/*為統(tǒng)計字符串常量中的字符個數(shù)初始化*/if(t->st!=NULL)free(t->st)；/*釋放t空間*/while(chars[i]!=‘\0’)/*統(tǒng)計chars中字符個數(shù)*/i++;len=i;if(！len){printf(“串常量為空串\n”)；t->st=NULL;t->length=0;}elsereturn

(0);if(!(t->st=(char

*)malloc(i*sizeof(char))))for(i=0；i<len；i++)/*逐字符賦值*/t->st[i]=chars[i];t->length=len;}return

(1);}

/*StrAssign*/第四章

串（2）串聯(lián)接StrConcat(t，s1，s2)StrConcat(HeapString

*t，HeapString

*s1，HeapString

*s2){if(t->st!=NULL)free(t->st)；/*釋放t原空間*/if

(!(t->st=(char

*)malloc(（s1->length+s2->length）*sizeof(chreturn(0);for(i=0；i<s1->length；i++)/*逐字符賦值*/t->st[i]=s1->st[i];for(i=0；i<s2->length；i++)/*逐字符賦值*/t->st[s1->length+i]=s2->st[i]；t->length=s1->length+

s2->length；return

(1);}

/*StrConcat

*/第四章

串（3）求子串SubString(t,s,pos,len)SubString(HeapString

*

t，

HeapString

*

s，

int

i，

int

len){if((pos<1)||(pos>s->length)||

(len<0)

||

(len>s->length-pos+1)){printf(“子串位置或長度有錯誤\n”);return(0);}if(t->st!=NULL)free(t->st)；/*釋放t原空間*/if((len==0)/*空子串*/{

t->st

=NULL;t->length=0;}else{t->st=(char

*)malloc(len*sizeof(char);for(i=0；i<len；i++)/*逐字符賦值*/t->st[i]=

s->st[pos-1+i];t->length=len;}return

(1);}/*SubString*/第四章

串（4）插入函數(shù)StrInsert(s,pos,t)StrInsert(HeapString

*s，int

pos，HeapString

*t){int

i;char

*temp;if

(pos<0

||

pos>s->length

||

s->length=

=0)return(0);temp=(char

*)malloc((s->length

+

t->length)*sizeof(char));if

(temp=

=NULL)

return(0);for

(i=0；i<pos；i++)temp[i]=s->st[i];for

(i=0；i<t->length；i++)temp[i+pos]=t->st[i];for

(i=pos；i<s->length；i++)temp[i

+

t->length]=s->st[i];s->length+=t->length;free(s->st);s->st=temp;return

(1);}

/*StrInsert*/第四章

串（5）刪除函數(shù)StrDelete(s,pos,t)StrDelete(HeapString*s，int

pos，int

len){int

i;char

*temp;if

(pos<0

||

pos>(s->length-

len))return(0);temp=(char

*)malloc((s->length-

len)*sizeof(char));if

(temp=

=NULL)

return(0);for

(i=0;i<pos;i++)temp[i]=s->st[i];for

(i=pos；i<s->length-

len；i++)temp[i]=s->st[i+len];s->length=s->length-len;free(s->st);s->st=temp;return

(1);}

/*StrDelete*/第四章

串4.2.3串的塊鏈存儲表示順序串上的插入和刪除操作運(yùn)算需要移動大量的字符。因此，可以采用單鏈表方式來存儲串值，串的這種鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈串。但在利用鏈表存儲串值時，每個結(jié)點(diǎn)既可以存放一個字符，也可以存放多個字符，即存在一個“結(jié)點(diǎn)大小”的問題。結(jié)點(diǎn)的大小是指結(jié)點(diǎn)的數(shù)據(jù)域可存放字符的個數(shù)。如圖4.6中所示的鏈表，其結(jié)點(diǎn)大小分別為4和1。第四章

串一般的，為了提高存儲密度，可使每個結(jié)點(diǎn)存放多個字符。顯然，當(dāng)結(jié)點(diǎn)大小大于1時，由于串長不一定是結(jié)點(diǎn)大小的整數(shù)倍，最后一個結(jié)點(diǎn)的數(shù)據(jù)域不一定剛好全被串值填滿，此時就需要以特殊的字符如‘?！蚱渌姆谴底址畛洹Ｍǔ＃瑢⑦@種結(jié)構(gòu)中的結(jié)點(diǎn)稱為塊，相應(yīng)的鏈表稱為塊鏈結(jié)構(gòu)。塊鏈結(jié)構(gòu)的類型可定義如下：#define

BLOCKSIZE

8

/*塊大小定義*/typedef

struct

Blocknode/*塊類型定義*/{

char

data[BLOCKSIZE]；struct

Blocknode

*next

；}

BLOCK；typedef

struct/*塊鏈類型定義*/{

BLOCK

*head,*tail；int

length；}

BLString；BLString

*s，*p，*head；/*s，p，head為塊鏈指針類型*/第四章

串4.3串的模式匹配算法4.3.1串的簡單模式匹配算法設(shè)有兩個串s和t，在串s中查找值等于t的子串的過程稱為模式匹配，其中，s串稱為主串或目標(biāo)串，t串稱為模式串。若在主串s中存在模式為t的子串，則稱匹配成功，否則稱為匹配失敗。串的簡單模式匹配實(shí)際

上是子串的定位運(yùn)算，是一種帶回溯的模式匹配。例如，圖4.7給出了s=“ababcabcacbab”，t=“abcac”的簡單模式匹配過程。第四章

串第四章

串其模式匹配過程可描述為：設(shè)在某一趟匹配時，s串中的第i個字符與t串

中的第j個字符比較，若si≠tj，則應(yīng)有si-1=tj-1，si-2=tj-2，…，si-j+1=t1，如

4.8所示。因此，當(dāng)si與tj匹配失敗時，新的一趟匹配開始應(yīng)該是t1與si-j+2繼續(xù)進(jìn)行比較，i指針從當(dāng)前位置回溯到新位置。其基本思想是：首先從主串s的第start（1≤start≤StrLen(s)）個字符起模式串t的第一個字符進(jìn)行比較，若相等，則繼續(xù)比較后續(xù)字符，否則，從主

串s的下一個字符起再重新和模式t的第一個字符比較，依此類推，直至模式t

的每一個字符依次和主串s中的一個連續(xù)的字符序列相等時為止，此時稱匹配

成功，函數(shù)值為與模式t中第一個字符相等的字符在主串s中的位置；否則稱匹配不成功，函數(shù)值返回0。第四章

串算法描述如下：return

(int

StrIndex（SeqString

*s

，

SeqString

*

t，

int

start）/*在目標(biāo)串s中定位模式串t的位置*/{int

i，j;if

((start<1)||(

start+(*t).len>(*s).len)||(*t).len=

=0))else{

i=start；j=1；while((i<(*s).len)&&(j<(*t).len)){

if（(*s).ch[i]=

=(*t).ch[j]）{i+

+；

j+

+；}else{

i=i-j+2；

j=1；}}if

(j=

=(*t).len) return

(i-(*t).len)；else return

(0)；}}在上面算法中可以引入起始查找位置指針start，即從s串的start位置起始查找第一個與t串相同的子串，使函數(shù)更為通用。第四章

串該算法匹配過程由于存在回溯，算法的效率不高。在最好情況下，算法的時間復(fù)雜度為O(n+m)。在最壞情況下的時間復(fù)雜度為O(n×m)。最壞的情況是在每一趟匹配失敗時，都是模式t的最后一個字符與s中相應(yīng)的字符比較時才不相等。例如，當(dāng)模式串為“00000001”，而目標(biāo)串為“00000000000000000000000000000000000000000000000000001”時，整個匹配過程中指針i需回溯45次，在算法中while循環(huán)了46×8（index×m）次，算法的效率很低。有時，我們也將該算法稱為樸素的模式匹配。在下一節(jié)中，我們將介紹另一種較好的KMP模式匹配算法。第四章

串4.3.2一種改進(jìn)的模式匹配算法D.E.Knuth與V.R.Pratt和J.H.Morris同時發(fā)現(xiàn)通過對上一節(jié)的簡單模式匹配算法進(jìn)行一些改進(jìn)，就可以消除算法中主串s指針的回溯，完成串的模式匹配，而且算法可以在O(n+m)的時間數(shù)量級上完成串的模式匹配操作。人們把該改進(jìn)算法稱它為克努特－莫里斯－普拉特算法(簡稱為KMP算法)，如圖4.9模式匹配過程。可以看出，其改進(jìn)之處在于整個匹配過程對主串而言無需回溯，每當(dāng)某一趟匹配過程中出現(xiàn)字符比較不等即匹配失敗時，目標(biāo)串i指針不需要回溯，而是利用已得到的“部分匹配”的結(jié)果將模式向右移動盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較，從而消除回溯。第四章

串第四章

串一般的情況討論如下：假設(shè)主串s為“s1s2…sn”，模式串t為“t1t2...tm”，要設(shè)計一個無回溯的匹配算法，關(guān)鍵在于確定在匹配過程中，當(dāng)主串中si與tj比較不等（即“失配”）時，模式串t中的哪一個字符應(yīng)與si繼續(xù)進(jìn)行比較？假設(shè)將這個字符記做tk，顯然，有k<j成立且對于不同的j值，k值也不相同，而且這個k值與主串s無關(guān)，而只依賴于模式串t本身的前j個字符。若令next[j]=k，則當(dāng)next[j]>0時，表示一旦匹配過程中出現(xiàn)si與tj不相等時，可用t中的next[j]位置的字符繼續(xù)與si比較；若next[j]=0，則表示t中任何字符都不與si比較，需重新比較t1與s

i+1?？梢姡瑢τ谌魏蔚哪Ｊ酱畉而言，只要能確定next[j]（j=1，2，…，m）的值，就可以用來加速匹配過程。模式串的next函數(shù)的定義為：第四章

串next函數(shù)的意義是：若模式串t中存在滿足等式“t1t2…t

k-1”=“t

j-k+1

t

j-k+2…t

j-1”的兩個子串，則當(dāng)匹配過程中主串中第i個字符與模式中第j個字符比較不等時，僅需將模式向右移動至模式中的第k個字符和主串中的第i個字

符對齊，匹配僅需從模式中的第k個字符與主串中的第i個字符繼續(xù)比較即可，如圖4.10所示。另外，若在“t1t2...tj-1”中不存在首尾相等的子串，則k=1，表示一旦有si與tj不相等時，則用t1與si繼續(xù)進(jìn)行比較。特別地，若j=1，當(dāng)t1與si比較不相等時，此時不能繼續(xù)右移，只要將t1與s

i+1繼續(xù)比較即可進(jìn)行新一趟的匹配，所以在next定義中，next[j]=0。第四章

串同時，為使模式串t的右移不丟失任何匹配成功的可能，對于同時存在多個滿足以上性質(zhì)條件的k值應(yīng)取最大值，以使得移動的位數(shù)i-k最小。例如，圖4.11中，s=“aaaabbb”，t=“aaab”，當(dāng)s4與t4比較不相等時，k可取1，2和3，但只有k取3時才可保證不丟失成功的可能匹配。第四章

串在求得模式的next函數(shù)之后，匹配過程如下：若在匹配過程中有si=tj

成立，則i和j分別增加1，否則，i不變，即主串指針不回溯，而j退到

next[j]的位置再比較，即用tnext[j]與si繼續(xù)比較，若此時相等，則指針各自增加1，否則j再退到下一個next[next[j]]值的位置，依此類推，直至出現(xiàn)下列兩種可能的情況：一是j退到某個next值（next[next[...next[j]]]）時主串和模式串中的字符進(jìn)行比較，若相等，則指針各自增1繼續(xù)進(jìn)行匹配；另一種情況是j退到值為0（即模式的第一個字符“失配”），此時需將模式繼續(xù)向右移動一個位置，即從主串的下一個字符si+1起和模式重新開始匹配。例如，對于模式串t=“abaabcac”：（1）j=1，next[1]=0；j=2，沒有首尾相等的子串，next[2]=1；j=3，同樣，也沒有首尾相等的子串，next[3]=1；j=4，存在首尾相等的子串“a”，所以next[4]=2；…….其余類推，從而可求得t所對應(yīng)的next函數(shù)，如圖4.12（a）所示。匹配過程如圖4.12（b）所示。第四章

串第四章

串第四章

串KMP算法描述如下：int

KMP(SeqString

*s，

SeqString

*

t，

int

start){

if

((start

<1)||(

start

+(*t).len>(*s).len+1)||(*t).len=

=0)}return

(0)；else{i=

start；j=1；while

((i<=(*s).len)

&&(j<=(*t).len))if(

(j=

=0)||(s->ch[i]=

=t->

ch[j]

)){

++i；++j；}else

j=next[j]；if

(j>(*t).len)return(

i-(*t).len)；elsereturn

(0)；}}/*

KMP*/第四章串下面介紹模式串的next函數(shù)值的求解算法。由于模式串的next函數(shù)值僅取決于模式串本身而和主串無關(guān)，可以從分析其定義出發(fā)用遞推的方法求得next的函數(shù)值。由定義可得：next[1]=0現(xiàn)假設(shè)next[j]=k，這表明在模式串中存在下列關(guān)系：“t1t2…tk-1”=“tj-k+1tj-k+2…tj-1”其中，k為滿足1<k<j的某個值，并且不可能存在一個數(shù)k’且k’>k滿足上式。顯然，若能求得next[j+1]與next[j]的關(guān)系，就可以求得next函數(shù)。（1）若tk=tj

，則有：next[j+1]=k+1，從而

next[j+1]=next[j]+1第四章

串（2）若tk≠tj，此時可把求next函數(shù)的問題看成是一個模式匹配的問題，整個模式串既是主串又是模式串。在當(dāng)前匹配的過程中，當(dāng)tj≠tk時，應(yīng)該將模式向右移動至用模式中的第next[k]個字符和主串中的第j個字符相比較。此時，若next[k]=k’且tj=tk，1<k’<k<j，則：next[j+1]=k’+1，從而可得：next[j+1]=

next[k]+1同理，若tj≠t

k’，則將模式繼續(xù)向右移動直至將模式中第next[k’]個字符和tj對齊，….，依次類推，直至tj和模式中某個字符匹配成功或者不存在任何k’(1<k’<j)滿足上述等式，則：next[j+1]=1例如，對于圖4.12（a）中的模式串t，已求得前6個字符的next函數(shù)值，現(xiàn)要求next[7]的值。因?yàn)閚ext[6]=3，且t6≠t3，由next[3]=1可知，要比較t6和t1，這相當(dāng)于將模式串向右移動，由于t6≠t1而且next[1]=0，所以可得next[7]=1；同樣，t7=t1，得next[8]=2。第四章

串求next函數(shù)的算法如下：void

GetNext(SeqString

*t，int

&next[

])/*求模式串t的next函數(shù)值并存入數(shù)組next中*/{

int

i=1，j=0；next[1]=0；while

(i<(*t).len)if

((j=

=0)||(*t).ch[i]

=(*t).ch[j])）{++i；++j；next[i]=j；}elsej=next[j]；}/*GetNext*/該算法的時間復(fù)雜度為O（m）。第四章

串需要注意的是：KMP算法僅當(dāng)模式與主串之間存在許多“部分匹配”的情況下才顯得比算法StrIndex效率高一些，KMP算法的最大特點(diǎn)是在整個匹配過程中，指示主串的指針無需回溯，對主串僅需從頭至尾掃描一遍，這對于處理諸如從外設(shè)輸入的大文件等問題很有效，可以邊讀入邊匹配，而無需回頭重讀。前面定義的next函數(shù)在某些情況下尚有缺陷?？梢詫ι鲜龅?/p>

next函數(shù)算法進(jìn)行改進(jìn)，得到計算next函數(shù)修正值的算法，此時，匹配算法不變。第四章

串void

GetNextval(seqstring

*t，int

&next[

])/*求模式串t的next函數(shù)修正值并存入數(shù)組next

*/{

int

i=1，j=0；next[1]=0；；while

(i<(*t).len)if

((j=

=0)

||((*t).ch[