數(shù)據(jù)結構第四章-串

主要內容4.1簡單模式匹配算法4.2

KMP算法——效率較高的匹配算法學習方法建議：

本章內容的學習注重理解模式匹配算法的匹配過程。第四章

串數(shù)據(jù)結構第四章-串全文共25頁，當前為第1頁。引言一、基本概念二、簡單模式匹配算法(BF算法)三、算法分析四、BF算法的特點小結在BF算法的比較過程中，可能產生回溯，故算法的漸近時間復雜度為O(n*m)。4.1簡單模式匹配算法數(shù)據(jù)結構第四章-串全文共25頁，當前為第2頁。一、基本概念

串是一種特殊的線性表，它特殊在：數(shù)據(jù)元素都是來自字符集！由于數(shù)據(jù)元素特殊，它的操作有些不同于一般線性表，例如：操作的對象一般是子串（即一組數(shù)據(jù)元素）而不是單個數(shù)據(jù)元素！有些高級語言已經把串ADT物理實現(xiàn)了，所以，我們這里只是簡單討論一下串模式匹配。4.1簡單模式匹配算法子串：串中連續(xù)的任意個字符組成的子序列，稱為該串的子串；主串：包含子串的串；數(shù)據(jù)結構第四章-串全文共25頁，當前為第3頁。字符在串中的位置：字符在串中的序號（即第幾個數(shù)據(jù)元素）；子串在串中的位置：子串的第一個字符在主串中的位置；

串相等：兩個串的長度相等，且各對應位置處的字符都相等；例如，設A和B分別為A=“Thisisastring!”，B=“is”

則A的長度為17，B的長度為2；B是A的子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對應的主串位置是3。因此，稱B在A中的序號（或位置）為3。模式匹配：子串的定位操作通常稱作串的模式匹配。在一個主串中，查找子串是否存在，存在返回子串在主串中的位置；不存在返回0。子串稱為模式串。數(shù)據(jù)結構第四章-串全文共25頁，當前為第4頁。5二、簡單模式匹配算法(BF算法)

采用回溯法：從主串的第i個位置開始，與子串的每個字符逐個比較，若均相等，則找到，位置為i；否則，即在某個位置出現(xiàn)了不等，則說明從該起點開始的子串不是模式串，換一個新起點，重新開始，繼續(xù)逐一比較，直到找到，或i>=Length為止。

TPij數(shù)據(jù)結構第四章-串全文共25頁，當前為第5頁。6第1趟

Tabbaba Paba

第2趟

Tabbaba P

aba

i=2j=2i=1j=0第3趟

Tabbaba Paba

第4趟

Tabbaba P

aba

i=2j=0i=6j=3每趟：

主串回溯到上次起點的下一個位置；模式串回到0

數(shù)據(jù)結構第四章-串全文共25頁，當前為第6頁。7三、算法分析：設目標串長度為n，模式串長度為m。1.在匹配成功時，即T串中肯定包含P串，則：(1)最好情況下：模式P出現(xiàn)在T的最開始，O(m)T:aaaaabbbbbbP:aaa(2)最壞情況下：模式P出現(xiàn)在T的最后①無回溯，最后是模式串，O(n)T:cbbbcbcbaaaP:aaa②有回溯，每次比較時，只有P的最后一個字符出現(xiàn)不等

T:aaaaaaaaaaaabP:aaaab

O(n*m)數(shù)據(jù)結構第四章-串全文共25頁，當前為第7頁。82.在匹配不成功時，即T串中不包含P串，則：(1)最好情況下：模式P的第一個字符就沒在T中出現(xiàn)，O(n)T:aaaaaaaaaaaaP:xyz(2)最壞情況下：只有P的最后一個字符匹配不上，而其它字符每次都匹配上，O(n*m)T:aaaaaaaaaaaaaP:aaaab數(shù)據(jù)結構第四章-串全文共25頁，當前為第8頁。四、BF算法的特點：

a.時間復雜性為O(n*m)。

b.由于有回溯，所以主串輸入后必須保存。改進：首尾匹配算法基本思想：先比較第一個字符，再比最后一個字符，若相等，再比較第2到n-1個字符。最壞的情況是倒數(shù)第2個字符不同。由于仍然需要回溯，時間復雜度還是O(n*m)。

T:aaaaaaaaaaaaaP:aaaab數(shù)據(jù)結構第四章-串全文共25頁，當前為第9頁。引言一、KMP算法(BF算法)二、失敗函數(shù)的定義三、算法的特點四、改進NEXT值小結在KMP算法的比較過程中，不產生回溯，匹配失敗時，主串的指針不回溯，只要在模式串中找合適的字符（由失敗函數(shù)確定）與其比較即可，故算法的漸近時間復雜度為O(n)。4.2

KMP算法——效率較高的匹配算法數(shù)據(jù)結構第四章-串全文共25頁，當前為第10頁。一、改進的模式匹配算法——KMP算法（解決了回溯）

D.E.KnuthJ.H.MorrisV.R.PrattKMP算法的基本思想：

KMP算法最大的改進之處：在匹配失敗時，主串中的指針i不需要回溯，而是在模式中找出適當?shù)淖址^續(xù)比較。數(shù)據(jù)結構第四章-串全文共25頁，當前為第11頁。12假設主串為T=‘t0t1t2...tn-1’模式串為P=‘p0p1p2...pm-1’m<<n…TiPjk≠

在主串的第i個字符ti與模式中pj匹配失敗時，i不回退，而是在模式中找適當字符pk與ti繼續(xù)比較，pk與ti，pk+1與ti+1……..當然此pk不是任意的，得根據(jù)一定算法找出。數(shù)據(jù)結構第四章-串全文共25頁，當前為第12頁。13

運用KMP算法的匹配過程第1趟目標

a

c

abaabaabcacaabc

模式

a

baabcac

第2趟目標a

cabaabaabcacaabc

模式

a

baabcac

第3趟目標acabaab

a

abcacaabc

模式

abaab

c

ac

第4趟目標acabaab

a

abcac

aabc

模式

(ab)

a

abcac

數(shù)據(jù)結構第四章-串全文共25頁，當前為第13頁。主串：s=“abcaabbabcabaa”模式串：p=“abcabaa”第1趟:abcaabbabcabaai=4i=0,j=0abcabaaj=4第2趟:abcaabbabcabaai=4i=4,j=1abcabaaj=1第3趟:abcaabbabcabaai=6i=4,j=0abcabaaj=2第4趟:abcaabbabcabaai=6i=6,j=0abcabaaj=0第5趟:abcaabbabcabaai=14,j=7i=7,j=0abcabaa匹配成功數(shù)據(jù)結構第四章-串全文共25頁，當前為第14頁。假設在比較中，遇到一個不匹配字符t[i]<>p[j],主串不動，模式串向右滑動，使主串中的第i個字符與模式串中的第幾個字符比較？i

1j

TPx數(shù)據(jù)結構第四章-串全文共25頁，當前為第15頁。

i-k+1

i-1i

1

j-1j

TPx

假設此時應與模式中第k(k<j)個字符比較，則模式中前k-1個字符必須滿足：

‘p1p2…pk-1’=‘ti-k+1,ti-k+2…ti-1’k-1數(shù)據(jù)結構第四章-串全文共25頁，當前為第16頁。已經得到的部分匹配的結果，

‘pj-k+1pj-k+2…pj-1’=‘ti-k+1,ti-k+2…ti-1’所以,應該有：‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’,則下一次模式串應該從k開始比較。那么如何求k呢？1

j-1j

tpxki-k+1i-1數(shù)據(jù)結構第四章-串全文共25頁，當前為第17頁。從分析可知：p[1..k-1]是p[1..j]的最長的既是真前綴又是真后綴的子串（即長度小于j）所以，求k就是求p[1..j]中最長的既是真前綴又是真后綴的子串的長度。

k與主串無關??！

j=012345678910111213求失敗函數(shù)：abcaabbabcabaa-10001120123421數(shù)據(jù)結構第四章-串全文共25頁，當前為第18頁。19根據(jù)前面的分析，失敗函數(shù)可以定義為：

-1當

j=0時next[j]=max{k|0<k<j且‘p0p1...pk-1’=‘pj-k...pj-1’}非空

0其它情況jkk

k0pj-kpj-1二、失敗函數(shù)的定義數(shù)據(jù)結構第四章-串全文共25頁，當前為第19頁。20利用next失敗函數(shù)進行匹配處理：若在進行某一趟匹配比較時在模式P的第j位失配：如果j>0，那么在下一趟比較時模式串P的起始比較位置是pnext(j)，目標串T的指針不回溯，仍指向上一趟失配的字符；如果

j=0，則目標串T指針進一，模式串P指針回到p0，繼續(xù)進行下一趟匹配比較。j01234567Pabaabcacnext(j)-10011201數(shù)據(jù)結構第四章-串全文共25頁，當前為第20頁。21

運用KMP算法的匹配過程第1趟目標

a

c

abaabaabcacaabc

模式

a

baabcac

j=1next(1)=0，下次p0第2趟目標a

cabaabaabcacaabc

模式

a

baabcac

j=0下次p0,目標指針進1

第3趟目標acabaab

a

abcacaabc

模式

abaab

c

ac

j=5next(5)=2,

下次p2

j01234567Pabaabcacnext(j)-10011201數(shù)據(jù)結構第四章-串全文共25頁，當前為第21頁。22

第3趟目標acabaab

a

abcacaabc

模式

abaab

c

ac

j=5next(5)=2,

下次p2第4趟目標acabaab

a

abcacaabc

模式

(ab)

a

abcac

j01234567Pabaabcacnext(j)-10011201數(shù)據(jù)結構第四章-串全文共25頁，當前為第22頁。三、KMP算法的特點四、改進NEXT值

next[j]=k即si與pj比