定義
一種由Knuth(D.E.Knuth)、Morris(J.H.Morris）和Pratt(V.R.Pratt）三人設計的線性時間字符串匹配算法。這個算法不用計算變遷函數δ，匹配時間為Θ（n），隻用到輔助函數π[1，m]，它是在Θ（m）時間内，根據模式預先計算出來的。數組π使得我們可以按需要，“現場”有效的計算（在平攤意義上來說）變遷函數δ。粗略地說，對任意狀态q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了與a無關但在計算δ（q，a）時需要的信息。由于數組π隻有m個元素，而δ有Θ（m∣Σ∣）個值，所以通過預先計算π而不是δ，使得時間減少了一個Σ因子。
詳細闡述
當我們分析一個模式字符串時，例如：abcabcddes. 需要分析一下，每個字符x前面最多有多少個連續的字符和字符串從初始位置開始的字符匹配。然後+1就行了（别忘了，我們的字符串都是從索引1開始的）當然，不要相同位置自己匹配，默認第一個字符的匹配數是0。
設字符串為 x1,x2,x3...xn，其中x1，x2，x3，... xi，... xn均是字符，設ai為字符xi對應的整數。當且僅當滿足如下條件：字符串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，繼續從1開始匹配
------| | |-----------前面的字符和開始位置的字符相同，所以是2,3,4
-----------| | | |-------不匹配隻能取1。
希望能明白的是，如果開始字符是 Ch1的話，那麼我們就是要在串中第2個Ch1後面的位置開始自己和自己匹配，計算最大的吻合度。但是這個不是最優的，因為他沒有考慮aaaaaaaaaaaaaaaaaaab的情況，這樣前面會出現大量的1，這樣的算法複雜度已經和最初的樸素算法沒有區别了。所以稍微改動一下：和樸素算法相比，隻是修改一句話而已，但是算法複雜度從O(m*n) 變成了：O(m+n)。
實際應用
摘要
給定兩個串S和T，長分别m和n，本文給出了一個找出二串間最大匹配的算法。該算法可用于比較兩個串S和T的相似程度，它與串的模式匹配有别。
關鍵詞
模式匹配 串的最大匹配 算法
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
提出問題
字符串的模式匹配主要用于文本處理，例如文本編輯。文本數據的存儲（文本壓縮）和數據檢索系統。所謂字符串的模式匹配[2]，就是給定兩個字符串S和T，長度分别為m和n，找出T中出現的一個或多個或所有的S，在這方面已經取得了不少進展。本文從文本處理的另一個角度出發，找出兩個串的最大匹配，比較其相似程度。它主要應用于文本比較，特别是在計算機輔助教學中。顯然前者要找S的完全匹配，而後者并無此要求。例如，若S=ABCD，T=EFABCDX，那麼模式匹配的結果就是找出了T中的一個ABCD，而我們算法的結果就是S能與T的ABCD完全匹配，但是T中還有3個字符是比S多出來的，也就是說在S中有100%的字符與T中的匹配，而在T中有57%的字符與S中的匹配。若S= ABCDFE，T=AFXBECDY。則在模式匹配中S與T無匹配項，但在我們的算法中就能發現T中存在A，B，C，D，但D後不存在E，F。而且S中也存在A，B，C，D，且具有順序性。這樣就能公正地評價S，T的區别。得知其相似程度。
文章的組織如下：首先介紹基本定義和問題的描述；第三節是算法設計；最後是本文總結。
問題描述
設∑為任意有限集，其元稱為字符，w：∑→N為∑到N的函數，稱為∑的權函數（注：本文僅讨論權值恒為1的情況）。∑*為∑上的有限字符串集合，那麼對任意S，T∈∑*，設S=a1a2…am，T=b1b2…bn，m>0，n>0。記
則稱矩陣C為串S與T的匹配關系陣。
于是求串S與T的最大匹配，等價于求C中的一個最大獨立點集M，它滿足，若ci,j，ci',j'∈M，則i< i' 當且僅當j< j'，i=i'當且僅當j=j'。我們稱這樣的最大獨立點集為C的最大C-獨立點集。
例：設∑為所有字母的集合，對任意x∈∑，w（x）≡1，設S與T分别為：S=“BOOKNEWS”，T=“NEWBOOKS”。則我們可以得到S與T兩個匹配：
這裡=5；
這裡=4。
顯然為串S與T的最大匹配。
S與T的匹配關系陣C可表示如下：
其中帶圈的部分為一最大C-獨立點集。
設計
我們僅就權值為一的情況進行讨論。
設S和T為任意給定串，C為的S與T匹配關系陣，那麼由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為節點的一條路，滿足：對路中的任意兩節點，均有某一節點位于另一節點的右下方。稱這種路為右下行路。
于是求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（在上的節點用①表示），我們向右下方找路，可以發現，在第4列有兩個1，根據命題2，我們選擇上面的一個1，也就是說選擇第1行的那個1，而不要第2行的那個1。同時我們也發現在第1行也有兩個1，由命題3知，我們選擇左邊的那個1，即第4列的那個1。此時=BO。但是當我們的算法運行到第4行時，=BOOK，由于K在第3行第6列，而本行的1在第1列，在路最後一個節點K的左邊，那麼我們必須新建一條路ψ，因為我們并不能确定是否以後就有≥，當算法運行到第6行時，=BOOK，ψ=NEW，=4，=3，我們将S鍊到路上，此時我們得到最長右下行路=BOOKS，=5。這樣我們就可以計算出這兩個字符串的匹配程度。
在我們的算法設計過程中，用到了兩個技巧。技巧之一，矩陣C不用存儲，是動态建立的，節省了空間。技巧之二，本算法并不要求所有的S與T中所有的元素都相互進行比較，也并不存儲所有的右下行路，節省了時間和空間。由矩陣中1的出現情況可見，本算法所需的空間和時間都遠小于O（mn）
結束語
本文給出了一個與模式匹配不同的，具有若幹應用的，串的最大匹配算法，該算法已經在機器上實現，達到了預期的效果。本文僅讨論權值恒為1的情況，對于權值任意的情形不難由此得到推廣。
