串的模式匹配算法

關于串的模式匹配算法1第一頁，共二十一頁，編輯于2023年，星期日2算法目的：確定主串中所含子串第一次出現的位置（定位）4.3串的模式匹配算法

BF算法

（又稱古典的、經典的、樸素的、窮舉的）

KMP算法算法種類：帶回溯，速度慢避免回溯，匹配速度快，是全課程的亮點之一定位問題稱為串的模式匹配，典型函數為Index(S,T,pos)第二頁，共二十一頁，編輯于2023年，星期日3BF算法的實現—即編寫Index(S,T,pos)函數例1：

S=‘ababcabcacbab’，T=‘abcac’，pos=1，

求：串T在串S中第pos個字符之后的位置。

利用演示系統(tǒng)看BF算法執(zhí)行過程。BF算法設計思想：將主串S的第pos個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串S的下一字符（pos+1）起，重新與T第一個字符比較。直到主串S的一個連續(xù)子串字符序列與模式T相等。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值0.第三頁，共二十一頁，編輯于2023年，星期日4討論：若n為主串長度，m為子串長度，則串的BF匹配算法最壞的情況下需要比較字符的總次數為(n-m+1)*m＝O(n*m)一般的情況是：O(n+m)

推導方法：要從最好到最壞情況統(tǒng)計總的比較次數，然后取平均。BF算法的時間復雜度最好的情況是：一配就中！只比較了m次。能否加快子串（又稱模式串）的滑動速度？能！利用已部分匹配過的信息使主串S的指針i不必回溯，最壞情況也能達到O(n+m)請看KMP算法！最壞的情況是：主串前面n-m個位置都部分匹配到子串的最后一位，即這n-m位比較了m次，別忘了最后m位也各比較了一次，還要加上m！所以總次數為：(n-m)*m+m＝(n-m+1)*m第四頁，共二十一頁，編輯于2023年，星期日5KMP算法（特點：速度快）①

KMP算法設計思想②

KMP算法的推導過程③KMP算法的實現（關鍵技術:計算next[j]）④KMP算法的時間復雜度全書一大亮點！第五頁，共二十一頁，編輯于2023年，星期日6盡量利用已經部分匹配的結果信息，盡量讓i不要回溯，加快模式串的滑動速度。例：①KMP算法設計思想：

(參見教材P80-84）S=‘ababcabcacbab’T=‘abcac’S=‘ababca

bcacbab’T=‘abca

c’S=‘ababcabcacbab’T=‘abcac’Index_kmp的返回值應為i=6需要討論兩個問題：①如何由當前部分匹配結果確定模式向右滑動的新比較起點k？②模式應該向右滑多遠才是高效率的?iiikk

a

b

aa

b

ckiii-T[0]第六頁，共二十一頁，編輯于2023年，星期日7奇妙的結果：k僅與模式串T有關！②KMP算法的推導過程：（見教材P81）請抓住部分匹配時的兩個特征：兩式聯立可得：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’S=‘ababc

a

b

cacbab’T=‘a

b

cac’ik則T的k-1～1位＝S前i-1～i-(k-1)位

即(4-2）式含義設目前打算與T的第k字符開始比較(1)(2)‘T1…Tk-1’則T的j-1～j-(k-1)位＝

S前i-1～i-(k-1)位

即(4-3）式含義ikjS=‘ababc

a

bcacbab’T=‘ab

cac’剛才肯定是在S的i處和T的第j字符處失配‘Tj-(k-1)…Tj-1’截取一段，但k有限制，1<k<jk是追求的新起點加速的前提：T首與Tj處有相同子串注意：j為當前已知的失配位置，我們的目標是計算新起點k。式中僅剩一個未知數k，理論上已可解！第七頁，共二十一頁，編輯于2023年，星期日8根據模式串T的規(guī)律：‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’由當前失配位置j(已知)，可以歸納出計算新起點

k的表達式。next[j]＝0當j＝1時//不比較max{

k

|1<k<j

且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況討論：（1）next[j]的物理意義是什么？（2）next[j]具體怎么求？—即KMP算法的實現令k=

next[j]（k與j顯然具有函數關系），則取T首與Tj處最大的相同子串新起點

k怎么求？第八頁，共二十一頁，編輯于2023年，星期日9（1）

next[j]有何物理意義？next[j]函數表征著模式T中最大相同前綴子串和后綴子串（真子串）的長度?？梢?，模式中相似部分越多，則next[j]函數越大，它既表示模式T字符之間的相關度越高，也表示j位置以前與主串部分匹配的字符數越多。即：next[j]越大，模式串向右滑動得越遠，與主串進行比較的次數越少，時間復雜度就越低（時間效率）。next[j]＝max{

k

|1<k<j

且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}模式串從第1位往右直到K-1位模式串從j的前一位往左經過K-1位想一想：如果主串和模式均為二進制碼流，用KMP算法效果如何？T=‘abaabcac’再想一想：如果主串是外存中一個大文件，用KMP算法效果又如何？（2）next[j]具體怎么求？—即KMP算法的實現第九頁，共二十一頁，編輯于2023年，星期日10計算Next[j]的方法：

當j=1時，Next[j]=0；//Next[j]=0表示根本不進行字符比較當j>1時，Next[j]的值為：模式串的位置從1到j-1構成的串中所出現的首尾相同的子串的最大長度加1。無首尾相同的子串時Next[j]的值為1。//Next[j]=1表示從模式串頭部開始進行字符比較（2）

next[j]怎么計算？怎樣計算模式T所有可能的失配點j

所對應的

next[j]？第十頁，共二十一頁，編輯于2023年，星期日11從兩頭往中間比較

模式串T：abaabcac

可能失配位j：12345678新匹配位k=next[j]:next[j]＝0當j＝1時max{k|1<k<j

且‘T1…Tk-1’=‘Tj-(k-1)…Tj-1’}1其他情況01122312討論：j=1時,next[j]≡0；//屬于“j=1”情況;j=2時,next[j]≡1；//找不到1<k<j的k，屬于“其他情況”；剛才已歸納：j=3時,k={2}，只需查看‘T1’=‘T2’成立否，No則屬于其他情況

j=4時,k={2，3}，要查看‘T1’=‘T3’及‘T1T2’=‘T2T3’是否成立j=5時,k={2，3，4}，要查看‘T1’=‘T4’，‘T1T2’=‘T3T4’和‘T1T2T3’=‘T2T3T4’以此類推，可得后續(xù)next[j]值?？捎醚菔境绦蝌炞Cnext[j]與s無關，可以預先計算例：第十一頁，共二十一頁，編輯于2023年，星期日12下一個要討論的問題是：如何用遞推方式來求出最大相同子串的長度呢？換言之，如何讓電腦替我們求出最大相同子串呢？這個問題一旦解決，整個KMP算法就可以掌握得很透徹了。voidget_next(SStringT,int&next[]){//

//求模式串T的next函數值并存入數組next[]。i=1;next[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}elsej=next[j];}}//get_next遞推法編程，參見教材P83程序第十二頁，共二十一頁，編輯于2023年，星期日13求解next[j]流程圖（遞推）

i=1;j=0next[1]=0i<T[0]j==0||T[i]==T[j]++i;++j;next[i]=j;j=next[j];ENDYYNN第十三頁，共二十一頁，編輯于2023年，星期日注：遞歸與遞推的區(qū)別：遞推：由“小”到“大”遞進；遞歸：由“大”到“小”嵌套。遞歸法（第1章自測卷4.2題）：longintfact(n)intn;{longf;if(n>1)f=n*fact(n-1);elsef=1;return(f);}遞推法：fact=1;for(i=1;i<=n;i++)fact*=i;例如：求f(n)=n!第十四頁，共二十一頁，編輯于2023年，星期日15第一步，先把模式T所有可能的失配點j所對應的next[j]計算出來；第二步：執(zhí)行定位函數Index_kmp（與BF算法模塊非常相似）③KMP算法的實現—即Index()操作的實現IntIndex_KMP(SStringS,SStringT,intpos){//見教材P82

i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i,++j}//不失配則繼續(xù)比較后續(xù)字符

else{j=next[j];}//特點：S的i指針不回溯，而且從T的k位置開始匹配

}if(j>T[0])returni-T[0];//子串結束，說明匹配成功

elsereturn0;}//Index_KMP第十五頁，共二十一頁，編輯于2023年，星期日前面定義的next函數在某些情況下還是有缺陷的，例如模式aaaab與主串aaabaaaab匹配時的情況：S:aaabaaaabT:aaaabi:123456789aaaabaaaabaaaab討論：next[j]是否完美無缺？先用演示程序驗證似乎慢了一點？能否再提速？由此派生出next函數的改進算法T：aaaabj：12345

next[j]：01234先計算next[j]：此時效率不高的原因為：子串前4位相同時，主串字符若與其中一個不相等，則不必再與其余3個比較。而實際上還在依次比較。aaaab第十六頁，共二十一頁，編輯于2023年，星期日17voidget_nextval(SStringT,int&nextval[]){

//next函數修正值存入數組nextvali=1;nextval[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;If(T[i]!=T[j])nextval[i]=j;elsenextval[i]=nextval[j];}elsej=nextval[j];}}//get_nextvalnext函數的改進算法見教材P84算法4.8，稱為nextval

[j]第十七頁，共二十一頁，編輯于2023年，星期日18④KMP算法的時間復雜度注意：由于BF算法在一般情況下的時間復雜度也近似于O(n+m)，所以至今仍被廣泛采用。而此時KMP的情況是：由于指針i無須回溯，比較次數僅為n,即使加上計算next[j]時所用的比較次數m，比較總次數也僅為n+m=O(n＋m)，大大快于