基于MATLAB的數(shù)據(jù)結(jié)構(gòu)與算法-KMP課件

基于MATLAB《數(shù)據(jù)結(jié)構(gòu)與算法》?延邊大學(xué)信息管理專業(yè)(13級(jí))?崔基哲KMP模式匹配算法MATLAB編程之基礎(chǔ)算法3串的模式匹配算法一、基本概念1、模式匹配（定位）設(shè)有主串S和子串T（將S稱為目標(biāo)串，將T稱為模式串），在主串S中，從位置start開始查找，如若在主串S中找到一個(gè)與子串T相等的子串，則返回T的第一個(gè)字符在主串中的位置，否則返回-1。2、算法目的確定主串中所含子串第一次出現(xiàn)的位置（定位）3、算法種類KMP算法KMP模式匹配算法?

它是：在一個(gè)長(zhǎng)字符串中匹配一個(gè)短子串的無(wú)回溯算法。定義?

s:模式串,m:模式串的長(zhǎng)度?

text:要匹配的字符串,n:text的長(zhǎng)度?

設(shè)text:x1,x2,…xn,s:a1,a2,…am,則當(dāng)存使xi+k=ak(k=1,2,…m)時(shí)，認(rèn)為text與模式串匹配，當(dāng)然text也可能與模式串有多處匹

配?

例如：text:abcabca,s:abc則text與s匹配位置有3和6KMP算法?作為一種無(wú)回溯的算法，它是高效的，待會(huì)兒你將看到它的時(shí)間復(fù)雜度為O(m+n)，空間復(fù)雜度也為O(m+n)?而且，它很容易理解，代碼也很短定義?

next:為對(duì)應(yīng)模式串的數(shù)組?

設(shè)字符串為s1s2s3...sm,其中s1，s2，s3，...si，...sm均是字符，則next[i]=m，當(dāng)且僅當(dāng)滿足如下條件：字符串s1s2...smequals字符串s(i-m+1)...si-1

si并且

s1s2...sm

s(m+1)unequals

s(i-m)s(i-m+1)...si-1

si。?

通俗地講，next[i]保存了以s[i]為結(jié)尾的后與模式串前綴的最長(zhǎng)匹配數(shù)。KMP算法的運(yùn)行過程?

我們用兩個(gè)指針i和j分別表示，A[i-j+1..i]與B[1..j]完全也就是說，i是不斷增加的，隨著i的增加j相應(yīng)地變化，且j滿足以A[i]結(jié)尾的長(zhǎng)度為j的字符串正好匹配B串的前j個(gè)字符（j當(dāng)然越大越好），現(xiàn)在需要檢驗(yàn)A[i+1]和B[j+1]的關(guān)系。?

如果a[i+1]==b[j+1],i和j各加1，什么時(shí)候j==m，就說B是A的子串（B串已經(jīng)整完了）KMP算法的運(yùn)行過程?

如果a[i+1]!=b[j+1],這時(shí)候怎么辦？?

i

=

1

2

3

4

5

6

7

8

9

……?

A

=

a

b

a

b

a

b

a

a

b

a

b

…?

B

=

a

b

a

b

a

c

bj

=

1

2

3

4

5

6

7j=5時(shí)，a[i+1]!=b[j+1],我們要把j改成比它小的值j‘。改多少合適呢？KMP算法的運(yùn)行過程?

i

=

1

2

3

4

5

6

7

8

9

……?

A

=

a

b

a

b

a

b

a

a

b

a

b

…?

B

=

a

b

a

b

a

c

bj

=

1

2

3

4

5

6

7?

記住，我們要保持A[i-j+1..i]與B[1..j]完全相等，因而j’最大的數(shù)使a[i-j’+1..i]與B[1..j’]完全相等.KMP算法的運(yùn)行過程?

i

=

1

2

3

4

5

6

7

8

9

……?

A

=

a

b

a

b

a

b

a

a

b

a

b

…?

B

=

a

b

a

b

a

c

bj

=

1

2

3

4

5

6

7?

顯然是求一個(gè)最長(zhǎng)的以i為末尾的后綴要與B的前綴匹配。由于A[i-j+1..i]與B[1..j]完全相等,故令j’=next[j]即可性質(zhì)保留KMP算法的運(yùn)行過程?

i

=

1

2

3

4

5

6

7

8

9

……?

A

=

a

b

a

b

a

b

a

a

b

a

b

…?

B

=

a

b

a

b

a

c

bj

=

1

2

3

4

5

6

7?

i

=

1

2

3

4

5

6

7

8

9

……?

A

=

a

b

a

b

a

b

a

a

b

a

b

…?B

=

a

b

a

b

a

c

bj

‘=

1

2

3

4

5

6

7KMP算法的運(yùn)行過程?

需要注意的是i并沒有動(dòng)，改變的只是j的值?

如果改變j的值后a[i+1]仍不等于b[j+1]的話，繼續(xù)改變j值直到a[i+1]==b[j+1]或者j=0?

j=0表示i+1前面無(wú)論怎么匹配都不能使

a[i+1]==b[j+1],只好讓a[i+1]與b[j+1]單獨(dú)匹配?

還是上一個(gè)例子，再演示一下KMP算法的運(yùn)行過程??i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

a

b

a

b

…??B

=j

=a

b

a

b

a

c

b1

2

3

4

5

6

7?

當(dāng)i=6,j=5時(shí)，a[i+1]!=b[j+1],故令

j=next[5]=3KMP算法的運(yùn)行過程??i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

a

b

a

b

…??B

=j

=a

b

a

b

a

c

b1

2

3

4

5

6

7?

此時(shí)i=6,j=3仍不滿足a[i+1]==b[j+1]，故繼續(xù)減小j,使j=next[3]=1KMP算法的運(yùn)行過程??i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

a

b

a

b

…??B

=j

=a

b

a

b

a

c

b1

2

3

4

5

6

7?

此時(shí)i=6,j=1仍不滿足a[i+1]==b[j+1]，故繼續(xù)減小j,使j=next[1]=0KMP算法的運(yùn)行過程??i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

a

b

a

b

…??B

=j

=a

b

a

b

a

c

b1

2

3

4

5

6

7?

終于，A[8]=B[1]，i變?yōu)?，j為1KMP算法的運(yùn)行過程??i

=

1

2

3

4

5

6

7

8

9

……A

=

a

b

a

b

a

b

a

d

b

a

b

…??B