模式匹配的一般算法模式匹配：子串的定位操作基本思想：從主串s

的第一個(gè)字符起和模式的第一個(gè)字符比較之，若相等，則繼續(xù)逐個(gè)比較后序字符，否則從主串的第二個(gè)字符起再重新和模式的字符比較之。依次類推，續(xù)字符序列相等，則稱匹配成功，否直至模式t

中的每個(gè)字符依次和主串s

中的則匹配不成功。算法FUNC

index_BF(s,t:strtp):integer;{求模式串

t

在主串

s

中的位置的定位函數(shù)

}I:=1;

j:=1

{指針初始化

}while

(

I

<=

s.curlen

)

and

(

j<=

t.curlen)

DOIF

s.ch

[I]

=

t.ch

[j]THEN

[

I:=I+1

;

j:=j+1]

{繼續(xù)比較后續(xù)字符}ELSE

[I:=I-j+2; j:=1];

{指針后退重新匹配}IF

j>

t.curlen

THEN RETURN

(I-t.curlen

) ELSE

RETURN(0)ENDF;{

index_BF

}特點(diǎn)

：一般情況下時(shí)間復(fù)雜度為O（n+m)，

的情況下為

O(n*m):

主串中存在多個(gè)和模式串“部分匹配”的子串，引起指針I(yè)

的多次回溯。如模式串為‘00000001’

主串為‘0000000000000000000000000000000000000000000000000000000000001’模式匹配的改進(jìn)算法---KMP算法對(duì)普通算法的改進(jìn)：每當(dāng)一趟匹配過(guò)程中出現(xiàn)字符比較不等時(shí)，不需回溯I指針，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式向右

“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。改進(jìn)算法的匹配過(guò)程示例I=3第三趟匹配

a

b

a

b

c

a

b

c

a

c

b

a

ba

b

c

a

c第一趟匹配abab

cabc

acba

babcJ=3II=7第二趟匹配abab

cabc

acba

bJ=5a b

c

a

cJ=1IJ=2J=6I=11主串為‘S1S2…Sn’,

模式串為‘P1P2…Pm’

,為了實(shí)現(xiàn)改進(jìn)算法，需要解決如下問(wèn)題當(dāng)主串中的第I

個(gè)字符與模式中第J

個(gè)字符比較不等時(shí)，主串中第I

字符（指針不回溯）應(yīng)與模式中哪個(gè)字符再比較（模式串向右滑行）？如何求J對(duì)應(yīng)的K？假設(shè)此時(shí)應(yīng)與模式中第K個(gè)（k<j)字符比較，則模式中前K-1個(gè)字符的子串必須滿足下列關(guān)系式，且不可能存在K’>K滿足下列關(guān)系式：‘P1P2…Pk-1’=‘Si-k+1Si-k+2…Si-1’因?yàn)椴糠制ヅ涞慕Y(jié)果是‘Pj-k+1Pj-k+2…Pj-1’=‘Si-k+1Si-k+2…Si-1’所以‘P1P2…Pk-1’=

‘Pj-k+1Pj-k+2…Pj-1’若模式串中存在滿足上式的兩個(gè)子串，則當(dāng)匹配過(guò)程中第I

個(gè)字符與模式中第J

個(gè)字符比較不等時(shí)，僅需將模式向右滑動(dòng)至模式中第K個(gè)字符和主串中第I

個(gè)字符對(duì)齊若令next[

j]=k,則next[

j]

表明當(dāng)模式中第J個(gè)字符與主串中相應(yīng)字符比較不等時(shí)，在模式中需重新和主串中該字符進(jìn)行比較的字符位置。0

當(dāng)J=1時(shí)Next[j]= Max

{k|

1<k<j

且‘P1…Pk-1’=‘Pj-k+1…Pj-1’J1

其他情況1

2

3

4

5

6

7

8a

b

a

a b

c

a

c0

1

1

2 2

3

1

2示例：模式串Next[j]KMP算法FUNC

index_KMP(s,t:strtp):integer;

{利用模式串的next函數(shù)求模式串T

在主串

s

中位置的KMP算法

}I:=1;

j:=1 {

指針初始化

}while

(

I

<=

s.curlen

)

and

(

j<=

t.curlen)

DOIF

（j=0)

OR (

s.ch

[I]

=

t.ch

[j]

)THEN

[

I:=I+1

;

j:=j+1] {

繼續(xù)比較下一對(duì)字符

}ELSE j:=next

[

j]

{模式串向右滑動(dòng)}IF

j>

t.curlen

THEN RETURN

(I-t.curlen

) ELSE

RETURN(0)ENDF;{

index_kmp

}如何求模式串next函數(shù)？next

函數(shù)的求法next

函數(shù)值僅取決于模式串本身而和相匹配的的主串無(wú)關(guān)從定義出發(fā)用遞推的方法求得next

函數(shù)值：next[1]=

0next[

j]=k

表明在模式串中‘P1P2…Pk-1’=‘Pj-k+1…Pj-1’其中k為滿足1<

k

<

j的某個(gè)值，不可能存在等式k’>k

滿足等式。求

Next[j+1]①若Pk=Pj,則表明在模式串中‘P1P2…Pk’=‘Pj-k+1…Pj’

不可能存在k’>k，滿足等式②若NPkex≠tP[j,+則1]表=k明+1在=n模ex式t[串j]+中1

‘P1P2…Pk’≠‘Pj-k+1…Pj’

此時(shí)可把next

函數(shù)值的問(wèn)題看成是一個(gè)模式匹配的問(wèn)題，整個(gè)模式串既是主串又是模式串。已有‘P1P2…Pk-1’=

‘Pj-k+1…Pj-1’

則當(dāng)Pk≠Pj時(shí)，應(yīng)將模式向右滑動(dòng)至以模式中的第next[k]個(gè)字符和主串中的第J

個(gè)字符相比較。若Pj=Pnext[k],則next[j+1]=next[

k]+1若Pj≠Pnext[k],則將模式繼續(xù)向右滑動(dòng)直至模式中第next[next[k]]個(gè)字符與Pj對(duì)齊…依次類推，直至Pj

和模式中某個(gè)字符匹配成功或者不存在任何K’（1

<K’<

J)滿足部分匹配，則有next[j+1]=1求next函數(shù)值的算法PROC

get--next(t:strtp;VAR

next

:ARRAY

[1..t.curlen]

of

integer){求模式串t

的next函數(shù)值并存入數(shù)組next

}j:=1;

k:=0;

next[1]:=0

{初始化

}while j<=

t.curlen

DOIF

（k=0)

OR (t.ch

[j]

=

t.ch

[k]

)THEN

[ j:=j+1;

k:=k+1;

next[