串的匹配算法.ppt

《串的匹配算法.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、4.４串的模式匹配算法一、基本概念1、模式匹配（定位）設(shè)有主串S和子串T（將S稱為目標(biāo)串，將T稱為模式串），在主串S中，從位置start開始查找，如若在主串S中找到一個與子串T相等的子串，則返回T的第一個字符在主串中的位置，否則返回-1。2、算法目的確定主串中所含子串第一次出現(xiàn)的位置（定位）3、算法種類BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）KMP算法1二、Brute-Force算法1、Brute-Force算法的設(shè)計思想：將主串S的第一個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串S的下

2、一字符起，重新與T第一個字符比較。直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值–1。2、Brute-Force算法的實現(xiàn)typedefstruct{charstr[MaxSize];intlength;}String;2intBFIndex(StringS,intstart,StringT){inti=start,j=0,v;while(i

3、;}else{i=i-j+1;j=0;}}if(j==T.length)v=i-T.length;elsev=-1;returnv;}33、BF算法的時間復(fù)雜度討論：若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數(shù)為(n-m+1)*m＝O(n*m)最好的情況是：一配就中！只比較了m次。最惡劣情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！所以總次數(shù)為：(n-m)*m+m＝(n-m+1)*m能否利用已部分匹配過的信息而加快

4、模式串的滑動速度？能！而且主串S的指針i不必回溯！最壞情況也能達到O(n+m)請看KMP算法！4盡量利用已經(jīng)部分匹配的結(jié)果信息，盡量讓i不要回溯，加快模式串的滑動速度。例：三、KMP算法１、KMP算法設(shè)計思想：S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’需要討論兩個問題：①如何由當(dāng)前部分匹配結(jié)果確定模式向右滑動的新比較起點k？②模式應(yīng)該向右滑多遠才是高效率的?iiikkabaabckii5奇妙的結(jié)果：k僅與模式串T

5、有關(guān)！請抓住部分匹配時的兩個特征：兩式聯(lián)立可得：“T0…Tk-1”=‘Tj-k…Tj-1’S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’ik則T的k-1～０＝S前i-1～i-k)位設(shè)目前打算與T的第k字符開始比較(1)(2)‘T０…Tk-1’則T的j-1～j-k位＝S前i-1～i-k)位ikjS=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’剛才肯定是在S的i處和T的第j字符處失配‘Tj-k…Tj-1’截取一段，但k有限制，0

6、未知數(shù)k，理論上已可解！6根據(jù)模式串T的規(guī)律：“T0…Tk-1”=“Tj-k…Tj-1”由當(dāng)前失配位置j(已知)，可以歸納計算新起點k的表達式。next[j]＝-1當(dāng)j＝0時max{k

7、0

8、7next[j]函數(shù)表征著模式T中最大相同前綴子串和后綴子串（真子串）的長度?？梢姡Ｊ街邢嗨撇糠衷蕉啵瑒tnext[j]函數(shù)越大，它既表示模式T字符之間的相關(guān)度越高，也表示j位置以前與主串部分匹配的字符數(shù)越多。即：next[j]越大，模式串向右滑動得越遠，與主串進行比較的次數(shù)越少，時間復(fù)雜度就越低（時間效率）。再想一想：如果主串是外存中一個大文件，用KMP算法效果又如何？8從兩頭往中間比較例：模式串T：abaabcac可能失配位j：01234567新匹配位k=next[j]:next[j]＝0當(dāng)j＝1時max{k

9、1

10、且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況-10011201討論：j=0時,next[j]≡-1；//屬于“j=1”情況;j=1時,next[j]≡0；//找不到0