數(shù)據(jù)結(jié)構(gòu)第四章

第四章串※教學(xué)內(nèi)容：串的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)；串操作的實現(xiàn)※教學(xué)重點：串的七種基本運算的定義，利用這些基本運算來實現(xiàn)串的其它各種運算的方法；在順序存儲結(jié)構(gòu)和在堆存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法；KMP算法，熟悉NEXT函數(shù)和改進NEXT函數(shù)的定義和計算?！虒W(xué)難點：KMP算法，手工計算NEXT函數(shù)和改進

NEXT函數(shù)的值。串類型的定義串的表示和實現(xiàn)串的模式匹配算法第四章

串4.1

串類型的定義一、串的定義二、串的抽象數(shù)據(jù)類型的定義一、串的定義串(string)(或字符串），是由零個或多個字符組成的有限序列。一般記為s=‘a(chǎn)1a2a3…an’

(n≥0)其中,s是串名,單引號括起來的字符序列是串的值；ai可以是字母,數(shù)字或其他字符;串中的字符個數(shù)稱為串的長度;零個字符的串稱為空串（Null

string)，其長度為零;

串中任意個連續(xù)的字符組成的子序列稱為該串的子串；包含子串的串相應(yīng)地稱為主串；字符在序列中的序號為該字符在串中的位置；子串在主串中的位置則以子串的第一個字符在主串中的位置來表示；由一個或多個空格字符組成的串稱為空格串；例：串a(chǎn),b,c,d,e五個串如下:a=“very

difficult”;b=“

”;c=“”;d=“very”;e=“difficult”;串a(chǎn)的長度為

;串b是長度為

的空格串;串c是空串,長度為

;串d和e是串a(chǎn)的子串，串d在串a(chǎn)中的位置是

，串e在串a(chǎn)中的位置是

。串相等：當(dāng)且僅當(dāng)兩個串的值相等，即只有當(dāng)兩個串的長度相等，并且各個對應(yīng)位置的字符都相等時才相等；空串是任意串的子串；任意串又是自己的子串注意：⑴串值必須用一對單引號括起來，但單引號本身不屬于串；⑵空串與空格串截然不同，空串不包含任何字符。二、串的抽象數(shù)據(jù)類型的定義如下：ADT

String

{數(shù)據(jù)對象：D＝{

ai

|ai∈CharacterSet,i=1,2,...,n, n≥0

}數(shù)據(jù)關(guān)系：R1＝{

<ai-1,

ai

>

|ai-1,

ai

∈D,i=2,...,n

}基本操作：SubString

(&Sub,

S,

pos,

len)ClearString

(&S)Index

(S,

T,pos)Replace

(&S,

T,

V)StrInsert

(&S,

pos,

T)StrDelete

(&S,

pos,

len)StrAssign

(&T,

chars)DestroyString(&S)StrCopy

(&T,

S)StrLength(S)StrCompare

(S,

T)Concat

(&T,

S1,

S2)StrEmpty

(S)}

ADT

StringStrAssign

(&T,

chars)初始條件：chars是字符串常量。操作結(jié)果：把chars賦為T

的值。StrCopy

(&T,

S)初始條件：串S

存在。操作結(jié)果：由串S

復(fù)制得串T。DestroyString

(&S)初始條件：串S

存在。操作結(jié)果：串S

被銷毀。StrEmpty

(S)初始條件：串S存在。操作結(jié)果：若S

為空串，則返回TRUE;否則返回FALSE。

表示空串，空串的長度為零。StrCompare

(S,

T)初始條件：串S

和T

存在。操作結(jié)果：若S

T，則返回值

0；若S

T，則返回值

0；

若S

T，則返回值

0。StrLength

(S)初始條件：串S

存在。操作結(jié)果：返回S

的元素個數(shù)，稱為串的長度。Concat

(&T,

S1,

S2)初始條件：串S1

和S2

存在。操作結(jié)果：用T

返回由S1

和S2聯(lián)接而成的新串。SubString

(&Sub,

S,

pos,

len)初始條件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作結(jié)果：用Sub

返回串S的第pos

個字符起長度為len的子串。子串為“串”中的一個字符子序列例如：SubString(

sub,

command

,

4,3)求得

sub

=

man

SubString(

sub,

command

,

1,7)求得

sub

=

command

SubString(

sub,

command

,7,1)求得

sub

=

d

SubString(sub,

commander

,

4,

7)sub

=

?SubString(

student

,

5,

0)

=SubString(sub,

beijing

,

7,

2)

=

?sub

=

?起始位置和子串長度之間存在約束關(guān)系長度為0

的子串為“合法”串

Index

(S,

T,

pos)初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作結(jié)果：若主串S

中存在和串T

值相同的子串,則返回T在主串S

中第pos個字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0。“子串在主串中的位置”意指子串中的第一個字符在主串中的位序。假設(shè)S

=

abcaabcaaabc

, T

=

bca

Index(S,

T,

1)

=2Index(S,

T,

3)

=6Index(S,

T,

8)

=0Replace

(&S,

T,

V)初始條件：串S,T和V

均已存在，且T

是非空串。操作結(jié)果：用V替換主串S中出現(xiàn)的所有與（模式串）T相等的不重疊的子串。例如Replace

(&S,T,V)：假設(shè)S=

abcaabcaaabca

，T=

bca

若V=

x

，則經(jīng)置換后得到S

=

axaxaax

若V=

bc

，則經(jīng)置換后得到S

=

abcabcaabc

StrInsert

(&S,

pos,

T)初始條件：串S和T存在，1≤pos≤StrLength(S)＋1。操作結(jié)果：在串S的第pos個字符之前插入串T。例如：

S

=

chater

，T

=

rac

，則執(zhí)行

StrInsert(S,4,

T)之后得到S

=

character

StrDelete

(&S,

pos,

len)初始條件：串S存在1≤pos≤StrLength(S)-len+1。操作結(jié)果：從串S中刪除第pos個字符起長度為len的子串。ClearString

(&S)初始條件：串S存在。操作結(jié)果：將S清為空串。對于串的基本操作集可以有不同的定義方法，在使用高級程序設(shè)計語言中的串類型時，應(yīng)以該語言的參考手冊為準(zhǔn)。例如：C語言函數(shù)庫中提供下列串處理函數(shù)：gets(str)

輸入一個串；puts(str)

輸出一個串；strcat(str1,

str2)

串聯(lián)接函數(shù)；strcpy(str1,

str2,

k)

串復(fù)制函數(shù)；strcmp(str1,

str2)

串比較函數(shù)；strlen(str)

求串長函數(shù)；在上述抽象數(shù)據(jù)類型定義的13種操作中，串賦值StrAssign、串復(fù)制Strcopy、串比較StrCompare、求串長StrLength、串聯(lián)接Concat以及求子串SubString等六種操作構(gòu)成串類型的最小操作子集。即：這些操作不可能利用其他串操作來實現(xiàn)，反之，其他串操作（除串清除ClearString和串銷毀DestroyString外）可在這個最小操作子集上實現(xiàn)。實現(xiàn)方法：例如，定位函數(shù)Index(S,T,pos)如何實現(xiàn)

?可利用串比較、求串長和求子串操作實現(xiàn)。StrCompare(SubString(S,

i,

StrLength(T)),T

)iposS

串T

串n-m+1T

串int

Index

(String

S,

String

T,

int

pos)

{// T為非空串。若主串S中第pos個字符之后存在與T相等的子串，//

則返回第一個這樣的子串在S中的位置，否則返回0if

(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

;//返回子串在主串中的位置else

return

i

;}//

while}//

ifreturn

0;}

//

Index//S中不存在與T相等的子串又如串的置換函數(shù)Replace(&S,T,V)：T

串V

串V

串pospossubinews

串subS

串串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以“單個元素”作為操作對象；在串的基本操作中，通常以“串的整體”作為操作對象。在程序設(shè)計語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。4.2

串的表示和實現(xiàn)串有三種機內(nèi)表示方法：一、串的定長順序存儲表示二、串的堆分配存儲表示

三、串的塊鏈存儲表示將串中的字符順序地存放在內(nèi)存一片連續(xù)的存儲單元中。設(shè)串S=‘a(chǎn)1

a2

...an’,則順序存貯結(jié)構(gòu)在內(nèi)存貯器中的存貯示意圖如圖所示:a1a2a3a

n一、串的定長順序存儲表示串的順序存貯結(jié)構(gòu)的兩種方式非緊縮存貯格式即一個字的存貯單元存放一個字符.緊縮存貯格式即一個字的存貯單元中放滿多個字符，然后在往下一個字存貯單元存放非緊縮存貯結(jié)構(gòu)programming存儲單元緊縮存貯結(jié)構(gòu)programming存儲單元與非緊縮存貯格式相比，緊縮存貯格式節(jié)省了存貯空間Status

Concat(SString

S1,

SString

S2,

SString

&T)

{//用T返回由S1和S2聯(lián)接而成的新串。若未截斷,則返回TRUE，否則FALSE。if

(S1[0]+S2[0]<=MAXSTRLEN){//未截斷T[1..S1[0]]=

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

=

S2[1..S2[0]];T[0]

=

S1[0]+S2[0]; uncut

=TRUE;

}}else

if

(S1[0]

<MAXSTRLEN)

{//截斷T[1..S1[0]]

=

S1[1..S1[0]];T[S1[0]+1..MAXSTRLEN]

=S2[1..MAXSTRLEN－S1[0]];T[0]

=

MAXSTRLEN;uncut

=FALSE;

}else

{//截斷(僅取S1)T[0..MAXSTRLEN]

=

S1[0..MAXSTRLEN];//

T[0]

==

S1[0]

==MAXSTRLENuncut

=

FALSE;return

uncut;}

//

Concat2.求子串SubString(&Sub,S,pos,len)求子串的過程即為復(fù)制字符序列的過程，將串S中從第pos個字符開始長度為len的字符序列復(fù)制到串Sub中。顯然，本操作不會有需截斷的情況，但有可能產(chǎn)生用戶給出的參數(shù)不符合操作的初始條件，當(dāng)參數(shù)非法時，返回ERROR。Status

SubString

(SString

&Sub,

SString

S,int

pos,int

len)

{//用Sub返回串S的第pos個字符起長度為len的子串.其中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)return

ERROR;Sub[1..len]=S[pos..pos+len-1];Sub[0]=len;returnOK;}//

SubString綜上兩個操作可見，在順序存儲結(jié)構(gòu)中，實現(xiàn)串操作的原操作為“字符序列的復(fù)制”，操作的時間復(fù)雜度基于復(fù)制的字符序列的長度。另一操作特點是，如果在操作中出現(xiàn)串值序列的長度超過上界MAXSTRLEN時，約定用截尾法處理，這種情況下不僅在求聯(lián)接串時可能發(fā)生，在串的其它操作中，如插入、置換等也可能發(fā)生。克服這個弊病唯有不限定串長的最大長度，即動態(tài)分配串值的存儲空間。仍以一組地址連續(xù)的存儲單元存放串值字符序

列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)

分配而得。在C語言中，存在一個稱之為“堆”的自由存儲區(qū)，并由C語言的動態(tài)分配函數(shù)malloc()和free()來管理。利用函數(shù)malloc()為每個新產(chǎn)生的串分配一塊實際串長所需的存儲空間，若分

配成功，則返回一個指向起始地址的指針，作為

串的基址。例：ch=(char*)malloc(len*sizeof(char))申請分配一個串長度為len

的存儲空間。二、串的堆分配存儲表示typedef

struct

{char

*ch;//若是非空串，則按串長分配存儲區(qū)，//否則ch為NULL//串長度int

length;}

HString;串的堆分配存儲表示：這類串操作實現(xiàn)的算法為：先為新生成的串分配一個存儲空間，然后進行串值的復(fù)制。例如：串復(fù)制操作StrCopy(&T,S)的實現(xiàn)算法是，若T已存在，則先釋放串T所占空間，當(dāng)串S不空時，首先為串T分配大小和串S長度相等的存儲空間，然后將串S的值復(fù)制到串T中；又如串插入操作StrInsert(&S,pos,T)的實現(xiàn)算法是，為串S重新分配大小等于串S和串T長度之和的存儲空間，然后進行串值復(fù)制，如下述算法：Status

SubInsert

(HString

&S,

int

pos,Hstring

T)

{//1≤pos≤StrLength(S)+1。在串S的第pos個字符之前插入串Tif

(pos<1||pos>S.length+1)return

ERROR;if

(T.length){//pos不合法//T非空，則重新分配空間，插入Tif

(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))exit(OVERFLOW);for

(i=S.length-1;i>=pos-1;i--)//為插入T而騰出位置，數(shù)組下標(biāo)//從0---S.length-1。S.ch[i+T.length]=S.ch[i];

//后移T.length個位置

S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];

//插入TS.length+=T.length;}return

OK;}

//

SubInsert以上兩種存儲表示通常為高級程序設(shè)計語言所采用。由于堆分配存儲結(jié)構(gòu)的串既有順序存儲結(jié)構(gòu)的特點，處理方便，操作中對串長又沒有任何限制，更顯靈活，因此，在串處理的應(yīng)用程序中也常被選用。以下所示為只含最小操作子集的Hstring串類型的模塊說明：基本操作的函數(shù)原型說明：Satus

StrAssign(

Hstring

&T,char

*chars);//生成一個其值等于串常量chars的串Tint

StrLength(Hstring

S);//返回S的元素個數(shù)，稱為串的長度int pare(Hstring

S,

Hstring

T);//若S>T，則返回值>0；//若S=T，則返回值=0；//若S<T，則返回值<0；Satus

ClearString(

Hstring

&S);//將S清為空串，并釋放S所占空間

Status

Concat

(Hstring

&T,Hstring

S1,Hstring

S2);//用T返回S1和S2聯(lián)接而成的新串

Hstring

SubString(Hstring

S,

int

pos,int

len);//1≤pos≤StrLength(S),且0≤len≤StrLength(S)-pos+1//返回串S的第pos個字符起長度為len的子串Status

Concat(HString

&T,

HString

S1,

HString

S2)

{//用T返回由S1和S2聯(lián)接而成的新串if

(T.ch)

free(T.ch);

//釋放舊空間if

(!(T.ch

=

(char

*)malloc((S1.length+S2.length)*sizeof(char))))exit(OVERFLOW);//分配失敗時退出T.ch[0..S1.length-1]

=

S1.ch[0..S1.length-1];T.ch[S1.length..T.length-1]

=

S2.ch[0..S2.length-1];T.length

=

S1.length

+

S2.length;return

OK;}

//ConcatStatus

SubString(HString

&Sub,

HString

S,int

pos,

int

len)

{//用Sub返回串S的第pos個字符起長度為len的子串if

(pos

<

1

||

pos

>

S.length

||

len

<

0

||

len

>

S.length-pos+1)return

ERROR;if

(Sub.ch)

free

(Sub.ch);//位置不合適//釋放sub的舊空間if

(!len)

//長度為0{Sub.ch=NULL; Sub.length=0;

}//空子串else

{

Sub.ch

=

(char

*)malloc(len*sizeof(char));Sub.ch[0..len-1]

=

S.ch

[pos-1..pos+len-2];//完整子串Sub.length

=

len;

}return

OK;}//SubString三、串的塊鏈存儲表示也可用鏈表來存儲串值，由于串結(jié)構(gòu)的特殊性——結(jié)構(gòu)中的每個數(shù)據(jù)域元素是一個字符，則用鏈表存儲串值時，存在一個“結(jié)點大小”的問題，即每個結(jié)點可以存放一個字符，也可以存放多個字符。當(dāng)結(jié)點大小大于1時。由于串長不一定是結(jié)點大小的整數(shù)倍，則鏈表中的最后一個結(jié)點不一定全被串值占滿，此時通常補上“#”或其它的非串值字符。結(jié)點大小為4的鏈表ABCDEFGHI###∧結(jié)點大小為1的鏈表ABCI∧//可由用戶定義的塊大小//結(jié)點結(jié)構(gòu)//串的鏈表結(jié)構(gòu)//串的頭和尾指針//串的當(dāng)前長度#define

CHUNKSIZE

80typedef struct

Chunk

{char

ch[CHUNKSIZE];struct

Chunk

*next;}

Chunk;typedef

struct

{Chunk

*head,

*tail;int

curlen;}

LString;為了便于進行串的操作，當(dāng)以鏈表存儲串值時，除頭指針外，還可附設(shè)一個尾指針指示鏈表中的最后一個結(jié)點，并給出當(dāng)前串的長度。稱如此定義的串存儲結(jié)構(gòu)為塊鏈結(jié)構(gòu)，說明如下：ABCDEFGHI###∧ABCI∧S.headS.headS.tailS.tail存儲密度=數(shù)據(jù)元素所占存儲位實際分配的存儲位在鏈?zhǔn)酱鎯Ψ绞街校Y(jié)點大小的選擇直接影響著串處理的效率。這要求我們考慮串值的存儲密度。顯然，存儲密度?。ㄈ缃Y(jié)點大小為1時），運算處理方便，然而，存儲占用量大。實際應(yīng)用時，可以根據(jù)問題所需來設(shè)置結(jié)點的大小。串值的鏈?zhǔn)酱鎯Y(jié)構(gòu)對某些串操作，如拼接操作等有一定方便之處，但總的說來不如另外兩種存儲結(jié)構(gòu)靈活，它占用存儲量大且操作復(fù)雜。實際應(yīng)用很少。子串的定位操作通常稱作串的模式匹配，其中，子串被稱作模式串。串的模式匹配是串的一種重要操作，很多軟件，若有“編輯”菜單項的話，則其中必有“查找”子菜單項。4.3串的模式匹配算法初始條件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作結(jié)果：若主串S中存在和串T值相同的子串返回它在主串S中第pos個字符之后第一次出

現(xiàn)的位置；否則函數(shù)值為0。首先，回憶一下串匹配(查找)的定義:INDEX

(S,

T,

pos)int

Index

(String

S,

String

T,

int

pos)

{// T為非空串。若主串S中第pos個字符之后存在與T相等的子串，//

則返回第一個這樣的子串在S中的位置，否則返回0if

(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

;else

return

i

;

//返回子串在主串中的位置}//

while}

//

ifreturn

0;}

//

Index下面討論以定長順序結(jié)構(gòu)表示串時的幾種INDEX

(S,

T,pos)算法。一、簡單算法二、首尾匹配算法三、KMP(D.E.Knuth,V.R.Pratt,

J.H.Morris)

算法一、簡單算法算法的基本思想：從主串S的第pos個字符起和模式T的第一個字符比較之，若相等，則繼續(xù)逐個比較后續(xù)字符，否則從主串的下一個字符起再重新和模式的字符比較之。依次類推，直至模式T中的每個字符依次和主串S中的一個連續(xù)的字符序列相等，則稱匹配成功，函數(shù)值為和模式T中第一個字符相等的字符在主串S中的序號，否則稱匹配不成功，函數(shù)值為零。int

Index(SString

S,

SString

T,

int

pos)

{}//Index算法時間復(fù)雜度為:O(m×n)

n為主串的長度，m為子串的長度，//返回子串T在主串S中第pos個字符之后的位置。若不存在，//則函數(shù)值為0。其中，T非空，1≤pos≤StrLength(S)。i=pos; j=1;while(i

<=S[0]

&&

j

<=T[0]){//S[0]存儲串的長度if

(S[i]

==

T[j])

{

++i;

++j;

}else

{

i

=

i-j+2;j

=

1;

}//繼續(xù)比較后繼字符//指針后退重新開始匹配}

//i指向比較完成后的下一個字符if

(j

>

T[0])

return

i-T[0];//說明j已經(jīng)比較完成else

return

0;第一趟匹配i=3ab

ab

cab

cacb

aba

b

c第三趟匹配ab

ab

cab

cacb

aba

b

c

a

ci

i=7j=1

j=5簡單算法的匹配過程示例(模式串T=‘a(chǎn)bcac’)第二趟匹配a

b

a

b

c

a

b

c

a

c

b

a

b(主串S)j=3i=2aj=1簡單算法的匹配過程示例(T=‘a(chǎn)bcac’)第四趟匹配ababcabcacbabi=4aj=1第五趟匹配第六趟匹配ababcabcacbabi=5ababcabcacbabaj=1i=6

i=11a

b

c

a

cj=6先比較模式串的第一個字符，再比較模式串的最后一個字符，最后比較模式串中從第二個到第n-1個字符。二、首尾匹配算法int

Index_FL(SString

S,SString

T,int

pos){//首尾匹配sLength=S[0]; tLength=

T[0]; i=pos;patStartChar

=

T[1]; patEndChar

=

T[tLength];while

(i

<=sLength

–tLength

+

1)

{if

(S[i]!=patStartChar)

++i;

//重新查找匹配起始點else

if

(S[i+tLength-1]

!=

patEndChar)

++i;//模式串的“尾字符”不匹配else

{k

=

1; j

=

2;//檢查中間字符的匹配情況while

(

j

<

tLength

&&

S[i+k]

==

T[j]){

++k;

++j;

}if

(

j

==

tLength

)

return

i;else

++i;

//重新開始下一次的匹配檢測}}return

0;}三、KMP(D.E.Knuth,

V.R.Pratt,J.H.Morris)

算法KMP算法的時間復(fù)雜度可以達到O(m+n)其改進在于：每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時，不需回溯i

指針，而是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較。第一趟匹配i=3ab

ab

cab

cacb

aba

b

c第二趟匹配ab

ab

cab

cacb

aba

b

c

a

cj=3i

i=7第三趟匹配ab

ab

cab

cacb

ab(a)bca

cj=1

j=5i

i=11j=2

j=6改進算法的匹配過程示例(T=‘a(chǎn)bcac’)當(dāng)S[i]<>T[j]

時，已經(jīng)得到的結(jié)果：S[i-j+1..i-1]

==

T[1..j-1]若已知則有T[1..k-1]

==

T[j-k+1..j-1]S[i-k+1..i-1]

==

T[1..k-1]即模式中頭k-1個字符的子串T[1..k-1]與主串中第

i個字符之前長度為k-1的子串S[i-k+1..i-1]相等，由此，匹配僅需從模式中第k個字符與主串中第i

個字符起繼續(xù)進行比較。定義：模式串的next函數(shù)若令next[j]=k，則next[j]表明當(dāng)模式中第j個字符與主串中相應(yīng)字符“失配”時，在模式中需要重新和主串中該字符進行比較的字符的位置。由此，

其它情況

Max{k |

1

k

j當(dāng)j

1時

0p

j-1

'}

pk

-1

'

'

p

j-k

1

且'p1p

2

1

next

[j]

……根據(jù)上述定義，計算下列模式串的next函數(shù)的值j

1

2

3

4

5

6

7

8模式串Next[j]

其它情況

Max{k |

1

k

j當(dāng)j

1時

0p

j-1

'}

pk

-1

'

'

p

j-k

1

且'p1p

2

1

next

[j]

……a

b

a

a

b

c

a

c0

1

1

2

2

3

1

2在求得模式的next函數(shù)之后，匹配可如下進行：假設(shè)以指針i和j分別指示主串S和模式P中正待比較的字符，令i

的初值為pos，j

的初值為1。若在匹配過程中，Si=pj，則i和j分別增1；否則，i不變，而j退到next[j]的位置再比較，若相等，則指針各自增1，否則j再退到下一個next值的位置，依次類推，直至下列兩種可能：一種是j退到某個next值時字符比較相等，則指針各自增1

繼續(xù)進行匹配；另一種是j

退到值為零（即模式的第一個字符“失配”），則此時需將模式繼續(xù)向右滑動一個位置，即從主串的下一個字符Si+1起和模式重新開始匹配。利用模式的next