"
文件在現代中無所不在，它們用來傳遞並發布訊息。從演算法設計的角度來看，這類的文件可視為簡單的字串。也就是說，它們可以抽象地看成一連串構成內容的字元。因此，要在這類資料上進行有趣的搜尋與處理，我們需要有效率的發法來處理字串。
字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡單了，傳統的字串搜尋是從關鍵字與字串的開頭開始比對。
[@more@]
Boyer-Moore 演算法
Boyer-Moore字串核對關鍵字的後面開始核對字串，並製作前進表，如果比對不符合則依前進表中的值前進至下一個核對處，假設是p好了，然後比對字串中p-n+1至p的值是否與關鍵字相同。
那麼前進表該如何前進，舉個實際的例子，如果要在字串中搜尋JUST這個字串，則可能遇到的幾個情況如下所示：
依照這個例子，可以決定出我們的前進值表如下：
|
其它 |
J |
U |
S |
T |
|
4 |
3 |
2 |
1 |
4（match） |
如果關鍵字中有重複出現的字元，則前進值就會有兩個以上的值，此時則取前進值較小的值，如此就不會跳過可能的位置，例如texture這個關鍵字，t的前 進值應該取後面的3而不是取前面的7。
我們將last(c)定義如下：
如果P包含c，則last(c)就是c出現在P之中最後一個位置(最右方)的索引值。否則，我們直接定義last(c) = -1。
Algorithm BMMatch(T,P)： Input：Strings T (text) with n characters and P (pattern) with m characters Output︰Strings index of the first substring of T matching P , or an indication that P is not a substring of T
compute function last
i ← m-1 j ← m-1 repeat if P[j] = T[i] then if j = 0 then return i //a match! else i ← i-1 j ← j-1 else i ← i+m-min( j,1+last(T[i]) ) //jump step j ← m-1 until i ﹥n-1 return “There is no substring of T matching P.”
Knuth-Morris-Pratt 演算法
KMP演算法是拿來處理字串是否相符。換句話說，給你兩個字串，你需要回答，B字串是否是A字串的子字串（A字串是否包含B字串）。比如，字串A="I'm matrix67"，字串B="matrix"，我們就說B是A的子字串。 解決這類問題，通常我們的方法是枚舉從A字串的什麼位置起開始與B字串比對，然後驗證是否相符。假如A字串長度為n，B字串長度為m，那麼這種方法的複雜度是O (mn)。雖然很多時候複雜度達不到mn（驗證時只看頭一兩個字母就發現不相符了），但我們有許多「最壞情況」，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我們將介紹的是一種最壞情況下O(n)的算法（這裡假設 m<=n），即KMP演算法之所以叫做KMP，是因為這個算法是由Knuth、Morris、Pratt三個提出來的，取了這三個人的名字的頭一個字母.假如，A="abababaababacb"，B="ababacb"。我們用i和j分別表示，A[i-j+ 1..i]與B[1..j]完全相等。也就是說，i是不斷增加的，隨著i的增加j相應地變化，且j滿足以A[i]結尾的長度為j的字串正好相對於B字串的前 j個字元（j當然越大越好），現在需要檢驗A[i+1]和B[j+1]的關係。當A[i+1]=B[j+1]時，i和j各加一；什麼時候j=m了，我們就說B是A的子字串，並且可以根據這時的i值算出相對的位置。當A[i+1]≠B[j+1]，KMP的策略是調整j的位置 （減小j值）使得A[i-j+1..i]與B[1..j]保持匹配且新的B[j+1]恰好與A[i+1]匹配（從而使得i和j能繼續增加）。我們看一看當 i=j=5時的情況。
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 此時，A[6]≠B[6]。這表明，此時j不能等於5了，我們要把j改成比它小的值j'。j'可能是多少呢？仔細想一下，我們發現，j'必須要使得B[1..j]中的頭j'個字母和末j'個字母完全相等（這樣j變成了j'後才能繼續保持i和j的性質）。這個j'當然要越大越好。在這裡，B [1..5]="ababa"，頭3個字母和末3個字母都是"aba"。而當新的j為3時，A[6]恰好和B[4]相等。於是，i變成了6，而j則變成了 4：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7 從上面的這個例子，我們可以看到，新的j可以取多少與i無關，只與B字串有關。我們完全可以預處理出這樣一個數組P[j]，表示當匹配到B數組的第j個字母而第j+1個字母不能匹配了時，新的j最大是多少。P[j]應該是所有B[1..P[j]]=B[j-P[j]+1..j]的最大值。再後來，A[7]=B[5]，i和j又各增加1。這時，又出現了A[i+1]≠B[j+1]的情況： i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7 由於P[5]=3，因此新的j=3： i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7 這時，新的j=3仍然不能滿足A[i+1]=B[j+1]，此時我們再次減小j值，將j再次更新為P[3]： i = 1 2 3 4 5 6 7 8 9 …… A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7 現在，i還是7，j已經變成1了。而此時A[8]居然仍然不等於B[j+1]。這樣，j必須減小到B[1]，即0： i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7 終於，A[8]=B[1]，i變為8，j為1。事實上，有可能j到了0仍然不能滿足A[i+1]=B[j+1]（比如A[8]="d"時）。因此，準確的說法是，當j=0了時，我們增加i值但忽略j直到出現A[i]=B[1]為止。 這個過程的代碼，我們在這裡列出：程式代碼j:=0;
for i:=1 to n do
begin
while (j>0) and (B[j+1]≠A[i]) do j:=P[j];
if B[j+1]=A[i] then j:=j+1;
if j=m then
begin
writeln('Pattern occurs with shift ',i-m);
j:=B[j];
end;
end;
最後的j:=P[j]是為了讓程式繼續做下去，因為我們有可能找到多處相符。 這個程式或許比想像中的要簡單，因為對於i值的不斷增加，程式碼用的是for迴圈。因此，這個程式虛擬碼可以這樣形象地理解：掃瞄字串A，並更新可以相對到B的什麼位置。 為什麼這個程式是O(n)的？其實，主要的爭議在於，while迴圈使得執行次數出現了不確定因素。我們將用到時間複雜度的攤還分析中的主要策略，簡單地說就是通過觀察某一個變量或函數值的變化來對零散的、雜亂的、不規則的執行次數進行累計。KMP的時間複雜度分析可謂攤還分析的典型。 我們從上述程式的j值入手。每一次執行while迴圈都會使j減小（但不能減成負的），而另外的改變j值的地方只有第五行。每次執行了這一行，j都只能加1；因此，整個過程中j最多加了n個1。於是，j最多只有n次減小的機會（j值減小的次數當然不能超過n，因為j永遠是非負整數）。這告訴我們，while迴圈總共最多執行 了n次。按照攤還分析的說法，平攤到每次for迴圈中後，一次for迴圈的複雜度為O(1)。整個過程顯然是O(n)的。這樣的分析對於後面P數組預備處理的過程同樣有效，同樣可以得到預處理過程的複雜度為O(m)。 預備處理不需要按照P的定義寫成O(m^2)甚至O(m^3)的。 我們可以P[1],P[2],...,P[j-1]的值來獲得P[j]的值。對於剛才的B="ababacb"，假如我們已經求出了P[1],P[2],P[3]和P[4]，我們應該怎麼求出P[5]和P[6]？P[4]=2，那麼P [5]顯然等於P[4]+1，因為由P[4]可以知道，B[1,2]已經和B[3,4]相等了，現在又有B[3]=B[5]，所以P[5]可以由P[4] 後面加一個字元得到。P[6]也等於P[5]+1嗎？顯然不是，因為B[ P[5]+1 ]≠B[6]。那麼，我們要考慮「退一步」了。我們考慮P[6]是否有可能由P[5]的情況所包含的子字串得到，即是否P[6]=P[ P[5] ]+1。下面為簡易說明： 1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ? P[5]=3是因為B[1..3]和B[3...5]都是"aba"；而P[3]=1則告訴我們，B[1]和B[5]都是"a"。既然P[6]不能由P[5]得到，或許可以由P[3]得到（如果B[2]恰好和B[6]相等的話，P[6]就等於P[3]+1了）。顯然，P[6]也不能通過P[3]得到，因為B[2]≠B[6]。事實上，這樣一直推到P[1]也不行，最後，我們得到，P[6]=0。 怎麼這個預先處理過程跟前面的KMP主程式這麼像呢？其實，KMP的預先處理本身就是一個B字串「自我配對」的過程。 它的代碼和上面的代碼神似：程式代碼P[1]:=0;
j:=0;
for i:=2 to m do
begin
while (j>0) and (B[j+1] ≠B[i]) do j:=P[j];
if B[j+1]=B[i] then j:=j+1;
P[i]:=j;
end; 最後補充一點：由於KMP算法只預先處理B字串，因此這種算法很適合這樣的問題：給定一個B字串和一群不同的A字串，問B是哪些A字串的子字串。"
