KMP算法是一種用于字符串匹配的算法，這個算法的高效之處在于當在某個位置匹配不成功的時候可以根據(jù)之前的匹配結(jié)果從模式字符串的另一個位置開始，而不必從頭開始匹配字符串。

定義

一種由Knuth - D.E.Knuth、Morris - J.H.Morris）和Pratt - V.R.Pratt）三人設(shè)計的線性時間字符串匹配算法。這個算法不用計算變遷函數(shù)δ，匹配時間為Θ（n），只用到輔助函數(shù)π[1，m]，它是在Θ（m）時間內(nèi)，根據(jù)模式預先計算出來的。數(shù)組π使得我們可以按需要，“現(xiàn)場”有效的計算（在平攤意義上來說）變遷函數(shù)δ。粗略地說，對任意狀態(tài)q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了與a無關(guān)但在計算δ（q，a）時需要的信息。由于數(shù)組π只有m個元素，而δ有Θ（m∣Σ∣）個值，所以通過預先計算π而不是δ，使得時間減少了一個Σ因子。

詳細闡述

當我們分析一個模式字符串時，例如：abcabcddes.?需要分析一下，每個字符x前面最多有多少個連續(xù)的字符和字符串從初始位置開始的字符匹配。然后+1就行了（別忘了，我們的字符串都是從索引1開始的）當然，不要相同位置自己匹配，默認第一個字符的匹配數(shù)是0。

設(shè)字符串為?x1,x2,x3…xn，其中x1，x2，x3，…?xi，…?xn均是字符，設(shè)ai為字符xi對應(yīng)的整數(shù)。當且僅當滿足如下條件：字符串x1x2…xm?equals?字符串x - i-m+1）…xi-1?xi?并且x1x2…xm?x - m+1）?unequals?x - i-m?x - i-m+1）…xi-1?xi，則a=m。

例如：

abcabcddes

0111234111

|———————-默認是0

–|?|?|—————–不能自己在相同位置進行字符匹配，所以這里認為沒有匹配字符串，所以0+1?=1，繼續(xù)從1開始匹配

——|?|?|———–前面的字符和開始位置的字符相同，所以是2,3,4

———–|?|?|?|——-不匹配只能取1。

希望能明白的是，如果開始字符是?Ch1的話，那么我們就是要在串中第2個Ch1后面的位置開始自己和自己匹配，計算最大的吻合度。但是這個不是最優(yōu)的，因為他沒有考慮aaaaaaaaaaaaaaaaaaab的情況，這樣前面會出現(xiàn)大量的1，這樣的算法復雜度已經(jīng)和最初的樸素算法沒有區(qū)別了。所以稍微改動一下：和樸素算法相比，只是修改一句話而已，但是算法復雜度從O - m*n?變成了：O - m+n。

實際應(yīng)用

摘要

給定兩個串S和T，長分別m和n，本文給出了一個找出二串間最大匹配的算法。該算法可用于比較兩個串S和T的相似程度，它與串的模式匹配有別。

關(guān)鍵詞

模式匹配?串的最大匹配?算法

Algorithm?on?Maximal?Matching?of?Strings

Lin?YuCai?Xiang?YongHong?Zhang?ChunXia?Zhang?JianJun

（Computer?Science?Department?of?Yunnan?Normal?University?Kunming?650092）

ABSTRACT?Given?Two?Strings?S?of?length?m?and?T?of?length?n，the?paper?presents?an?algorithm?which?finds?the?maximal?matching?of?them.?The?algorithm?can?be?used?to?compare?the?similarility?of?the?two?strings?S?and?T,it?is?different?with?the?strings'?pattren?matching.

KEY?WORDS?Pattern?Matching?Maximal?Matching?of?Strings?Algorithm

提出問題

字符串的模式匹配主要用于文本處理，例如文本編輯。文本數(shù)據(jù)的存儲（文本壓縮）和數(shù)據(jù)檢索系統(tǒng)。所謂字符串的模式匹配[2]，就是給定兩個字符串S和T，長度分別為m和n，找出T中出現(xiàn)的一個或多個或所有的S，在這方面已經(jīng)取得了不少進展。本文從文本處理的另一個角度出發(fā)，找出兩個串的最大匹配，比較其相似程度。它主要應(yīng)用于文本比較，特別是在計算機輔助教學中。顯然前者要找S的完全匹配，而后者并無此要求。例如，若S=ABCD，T=EFABCDX，那么模式匹配的結(jié)果就是找出了T中的一個ABCD，而我們算法的結(jié)果就是S能與T的ABCD完全匹配，但是T中還有3個字符是比S多出來的，也就是說在S中有100%的字符與T中的匹配，而在T中有57%的字符與S中的匹配。若S=?ABCDFE，T=AFXBECDY。則在模式匹配中S與T無匹配項，但在我們的算法中就能發(fā)現(xiàn)T中存在A，B，C，D，但D后不存在E，F(xiàn)。而且S中也存在A，B，C，D，且具有順序性。這樣就能公正地評價S，T的區(qū)別。得知其相似程度。

文章的組織如下：首先介紹基本定義和問題的描述；第三節(jié)是算法設(shè)計；最后是本文總結(jié)。

問題描述

設(shè)∑為任意有限集，其元稱為字符，w：∑→N為∑到N的函數(shù)，稱為∑的權(quán)函數(shù)（注：本文僅討論權(quán)值恒為1的情況）?！?為∑上的有限字符串集合，那么對任意S，T∈∑*，設(shè)S=a1a2…am，T=b1b2…bn，m>0，n>0。記<m>={1,2，…，m},<n>={1,2，…，n}，則稱{ - i,j）∣i∈<m>；，j∈<n>；，ai=bj}為S與T的匹配關(guān)系集，記作M（S，T），稱M為S與T的一個（容許）匹配，若對任意（i,j），（i',j'）∈，①?i<?i'，當且僅當j<?j'，②?i=?i'當且僅當j=?j'。S與T的匹配中滿足?最大者，稱為S與T的最大匹配。若C - i,j）為N上的m×n矩陣，且滿足：

則稱矩陣C為串S與T的匹配關(guān)系陣。

于是求串S與T的最大匹配，等價于求C中的一個最大獨立點集M，它滿足，若ci,j，ci',j'∈M，則i<?i'?當且僅當j<?j'，i=i'當且僅當j=j'。我們稱這樣的最大獨立點集為C的最大C-獨立點集。

例：設(shè)∑為所有字母的集合，對任意x∈∑，w（x）≡1，設(shè)S與T分別為：S=“BOOKNEWS”，T=“NEWBOOKS”。則我們可以得到S與T兩個匹配：

這里=5；

這里=4。

顯然為串S與T的最大匹配。

S與T的匹配關(guān)系陣C可表示如下：

其中帶圈的部分為一最大C-獨立點集。

設(shè)計

我們僅就權(quán)值為一的情況進行討論。

設(shè)S和T為任意給定串，C為的S與T匹配關(guān)系陣，那么由2的討論知，求S與T的最大匹配問題，等價于求C的最大C-獨立點集問題。因而，為了解決我們的問題，只要給出求C的最大C-獨立點集的算法就可以了。

顯然，為了求出C的最大C-獨立點集，我們可以采用這樣的方法：搜索C的所有C-獨立點集，并找出它的最大者。這種方法是可行的，但并不是非常有效的。這會使問題變得很繁，復雜度很大。因此，我們先對問題進行分析。

在下面的討論中，我們把C的任一C-獨立點集={ai1,j1，…，ais,js}，記作=ai1,j1…ais,js，i1?<；…<?is。于是可看作陣C中以1為節(jié)點的一條路，滿足：對路中的任意兩節(jié)點，均有某一節(jié)點位于另一節(jié)點的右下方。稱這種路為右下行路。

于是求C-獨立點集等價于求陣C的右下行路。這種求右下行路的搜索可以逐行往下進行。

命題1.?若?=αai,jβ和ψ=α'ai,jσ為C的兩個C-獨立點集，且α為α'的加細，則存在C-獨立點集'=αai,jδ，滿足≥。

命題2.?若?=αai,jβ和ψ=α'ai+k,jσ為C的兩個C-獨立點集，且≥，則存在C-獨立點集'=αai,jδ，滿足≥。

命題3.?若?=αai,jβ和ψ=α'ai,j+kσ為C的兩個C-獨立點集，且≥，則存在C-獨立點集'=αai,jδ，滿足≥。

由命題1知，在搜索右下行路的過程中，如果已獲得了某一C-獨立點集的某一初始截段αai,j和另一C-獨立點集ψ的某一初始截段α'ai,j，且有≤，則我們可以停止對ψ的進一步搜索。

由命題2知，在搜索右下行路的過程中，在某一列j存在某兩個C-獨立點集的某初始截段=ai1,j1…ais,j和ψ=al1,m1…alt,j，如果≥，但lt>is，則我們可以停止對ψ的進一步搜索。

由命題3知，在搜索右下行路的過程中，在某一行i存在某兩個C-獨立點集的某初始截段=ai1,j1…ai,js和ψ=ai1,m1…ai,mt，如果≥，但mt>js，則我們可以停止對ψ的進一步搜索。

由此可見，并不要求搜索所有C的最大C-獨立點集，而可以采用比這簡單得多的方法進行計算。那么按照我們上面的三個命題，來看如下實例：

首先我們得到=B（在上的節(jié)點用①表示），我們向右下方找路，可以發(fā)現(xiàn)，在第4列有兩個1，根據(jù)命題2，我們選擇上面的一個1，也就是說選擇第1行的那個1，而不要第2行的那個1。同時我們也發(fā)現(xiàn)在第1行也有兩個1，由命題3知，我們選擇左邊的那個1，即第4列的那個1。此時=BO。但是當我們的算法運行到第4行時，=BOOK，由于K在第3行第6列，而本行的1在第1列，在路最后一個節(jié)點K的左邊，那么我們必須新建一條路ψ，因為我們并不能確定是否以后就有≥，當算法運行到第6行時，=BOOK，ψ=NEW，=4，=3，我們將S鏈到路上，此時我們得到最長右下行路=BOOKS，=5。這樣我們就可以計算出這兩個字符串的匹配程度。

在我們的算法設(shè)計過程中，用到了兩個技巧。技巧之一，矩陣C不用存儲，是動態(tài)建立的，節(jié)省了空間。技巧之二，本算法并不要求所有的S與T中所有的元素都相互進行比較，也并不存儲所有的右下行路，節(jié)省了時間和空間。由矩陣中1的出現(xiàn)情況可見，本算法所需的空間和時間都遠小于O（mn）

結(jié)束語

本文給出了一個與模式匹配不同的，具有若干應(yīng)用的，串的最大匹配算法，該算法已經(jīng)在機器上實現(xiàn)，達到了預期的效果。本文僅討論權(quán)值恒為1的情況，對于權(quán)值任意的情形不難由此得到推廣。