KMP算法--字符串模式匹配算法
今天看到第四章《串》了，其中我覺得花的時間多一點(diǎn)的值得我寫篇隨筆的知識點(diǎn)就是：4.3?串的模式匹配算法；書上介紹了兩種字符串匹配算法，一種是最簡單最容易想到的逐個字符匹配算法（時間復(fù)雜度在好的情況下為O(n+m)，[n為原串，m為匹配串]，在最壞的情況下為O(n*m)），這個在我的代碼中有了，就不贅述了。另外一種就是KMP算法，話說是三個人同時想到的算法，這仨名字各取開頭的字符就是這個算法的名稱了。這個算法是模式匹配的改進(jìn)算法；（時間復(fù)雜度為O(m)）。
逐個字符匹配算法 1 int indexOf(string s,string t,int pos){//逐個字符匹配算法，從s串的pos位置開始,返回t出現(xiàn)的首位置2 if(t.empty()){//字串不要為空
3 return -1;
4 }
5 int i = pos;
6 int temp = 0;
7 for(;i<s.size();i++){
8 temp = i;
9 for(int j = 0;j<t.size();j++){
10 if(s[temp] == t[j]){//如果相等,就繼續(xù)循環(huán)下去
11 temp++;
12 if(j == (t.size()-1)){
13 return i;//返回出現(xiàn)的首位置
14 }
15 }else{//不相等
16 break;
17 }
18 }
19 }
20 }
而這個KMP算法在大體思想就是這樣：
注意： s為原串，t為模式串，即小一點(diǎn)的那個，后面都是一樣。↑↓
? ? ? ? ↓i=0 從這兒開始比較
1.s :?a c a b a?a b a a b c a c?a a b c
? ?t :?a b a a b c a c (紅色為t在s中第一次出現(xiàn))
?↑j=0 ? next[0]=-1 (next[]數(shù)組的作用等會兒說哈)
?
? ? ? ? ? ↓i=1
2.s :?a c a b a?a b a a b c a c?a a b c
? ?t :?a b a a b c a c
? ?↑j=1 ? next[1]=0 ? (發(fā)現(xiàn)c!=b,所以t串又要從頭來比較，后面的代碼就如下，j = next[j]; ?if(j==-1){j=0;)
? ? ? ? ? ↓i=1
3.s :?a?c?a b a?a b a a b c a c?a a b c
? ?t : ? ?a?b?a a b c a c
? ?↑j=1 ? next[1]=0 ?(發(fā)現(xiàn)c!=a，所以s串又要后退點(diǎn)了)
? ? ? ? ? ? ?↓i=2
4.s :?a?c a b a?a b a a b c a c?a a b c
? ?t : ? ? ?a?b?a a b c a c
? ? ? ↑j=0 ? next[0]=-1 ?(相等，好的繼續(xù))
? ? ? ? ? ? ? ? ? ? ? ? ? ↓i=7
5.s :?a?c?a?b a?a b a a b c a c?a a b c
? ?t : ? ? ?a?b?a a b?c?a c
? ? ? ? ? ? ? ? ? ?↑j=5 ? next[5]=2 ?(發(fā)現(xiàn)c!=a了，這時候就是體現(xiàn)算法的時候了，此時i會暫停向后移動，而t串應(yīng)該從哪里開始比較呢？next數(shù)組告訴了我們答案，從t[2]開始和s串i位置開始比較，如下圖)
? ? ? ? ? ? ? ? ? ? ? ? ? ↓i=7
6.s :?a?c?a?b a?a b a a b c a c?a a b c
? ?t : ? ? ? ? ? ? ?a?b?a?a b?c?a c
? ? ? ? ? ? ? ? ? ?↑j=2 ? next[2]=0 ?(后面的移動方式我沒必要畫了，很明顯已經(jīng)移到合適的地方了，乍一看很巧，細(xì)細(xì)一想還是很有智慧的)
?好，我來說說上面出現(xiàn)的每個參數(shù)的作用吧：s為原串，t為模式串，i為s串的移動指針，j為t串的移動指針，next數(shù)組的作用是指明t串指針j的位置的，也就是j回溯多少，當(dāng)S串中的第i個字符與t串中的第j個字符不等時，s串的第i個字符(i指針永遠(yuǎn)不會往回走，最多只是暫停下)應(yīng)該與模式中的哪個字符再比較的。針對每個t串，都會生成相對應(yīng)的next數(shù)組，而next如何生成？
請看next特征數(shù)組構(gòu)造:
??? 模式串t開頭的任意個字符，把它稱為前綴子串，如t0t1t2…tm-1。在t的第i位置的左邊，取出k個字符，稱為i位置的左子串，即ti-k+1... ti-2 ti-1 ti。求出最長的（最大的k）使得前綴子串與左子串相匹配稱為，在第i位的最長前綴串。第i位的最長前綴串的長度k就是模板串P在位置i上的特征數(shù)n[i]特征數(shù)組成的向量稱為該模式串的特征向量。
?? 可以證明對于任意的模式串t = t0t1…tm-1,確實(shí)存在一個由模式串本身唯一確定的與目標(biāo)串無關(guān)的數(shù)組next，計算方法為：
?? (1)? 求t0…ti-1中最大相同的前綴和后綴的長度k;
?? (2)? next[i] = k;
?? 作為特殊情況，當(dāng)i=0時，令next[i] = -1;顯然，對于任意i(0≤i<m)，有next[i] < i;假定已經(jīng)計算得到next[i], 那么next[i+1] = ? 特征數(shù)ni ( -1≤ ni ≤ i )是遞歸定義的，定義如下：
?? (1) n[0] ＝ -1，對于i > 0的n[i] ，假定已知前一位置的特征數(shù) n[i-1]＝ k ；
?? (2) 如果ti ＝ tk ，則n[i] ＝ k＋1 ；
?? (3) 當(dāng)ti ≠ tk 且k≠0時，則令k ＝ n [k -1] ; 讓(3)循環(huán)直到條件不滿足；
?? (4) 當(dāng)qi ≠ qk 且k ＝ 0時，則ni ＝ 0;
?? 根據(jù)以上分析，可以得到next特征數(shù)組的計算方法，算法代碼如下:
1 void getNext(string t,int* next){//求子字串t的next[]函數(shù)之并存入數(shù)組中2 int temp = 0;
3 int zm = 0;
4 for(int i = 0; i < t.size();i++){//從0開始循環(huán)
5 temp = i-1;
6 if(i == 0){//第一個的時候，為-1
7 next[i] = -1;
8 }else if(temp > 0){
9 for(int j = temp;j>0;j--){
10 if(equals(t,i,j)){
11 next[i] = j;
12 break;
13 }else{
14 next[i] = 0;//視為其他情況為0
15 continue;
16 }
17
18 }
19 }else{
20 next[i] = 0;//其他情況為0
21 }
22
23 }
24
25 }
26
27 bool equals(string t,int i,int j){//比較字符串t[0]~t[j-1]同t[i-j]~t[j]是否相等
28 int temp = i-j;
29 //if((j-1)==(2*j-i)){//如果長度相同
30 for(int k = 0; k < j; k++,temp++){
31 if(t[k]!=t[temp]){//如果有不相同的，返回false
32 return false;
33 }
34 }
35 return true;//運(yùn)行到這兒說明字符串t[0]~t[j-1]同t[i-j]~t[j]相等
36 }
? 到這里了，解決了一個點(diǎn)了，還有一個點(diǎn)就是，i串既然不回溯，還是有暫停的，至于暫?？偸怯羞@樣規(guī)律的：第一不匹配--停，第二次不匹配--走...針對i串的同一個字符沒有第三次哦，為什么？你懂的。
說到這兒，我想KMP算法的思想應(yīng)該講完了，看起來KMP算法是要好些，通常來說，模式串t的長度比S串的小的多，對于整個匹配算法來講，確實(shí)要改進(jìn)不少，雖然第一種算法的時間復(fù)雜度是O(n*m)，但是在一般的情況下，其實(shí)際執(zhí)行的時間按近似于O(n+m),所以至今很多地方也有采用；
總結(jié)：KMP算法在模式串t與主串s存在許多“部分匹配”的情況下才顯得速度很快，這個算法的最大特點(diǎn)就是，主串的指針不需要回溯，從頭掃一遍就行了，這對處理龐大的數(shù)據(jù)文件很有效，也可以邊讀入便匹配，無需回頭再重讀。
忘記貼代碼了，呵呵，補(bǔ)上：
1 /*2 2011-7-25 zhangming
3 第四章，串 4.3節(jié)-串的模式匹配算法
4 總的來說有兩種算法，
5 1，逐個字符匹配算法；（此匹配算法最簡單，時間復(fù)雜度在好的情況下為O(n+m)，[n為原串，m為匹配串]，在最壞的情況下為O(n*m)）
6 2，KMP算法；模式匹配的改進(jìn)算法；（時間復(fù)雜度為O(m)）
7 */
8 #include <iostream>
9 #include <string>
10 using namespace std;
11 int indexOf(string s,string t,int pos);//逐個字符匹配算法，從s串的pos位置開始,返回t出現(xiàn)的首位置
12 int indexOfKMP(string s,string t,int pos);//KMP算法；模式匹配的改進(jìn)算法；
13 void getNext(string t,int* next);//求子字串t的next函數(shù)之并存入數(shù)組中
14 bool equals(string t,int i,int j);//比較字符串t[0]~t[j-1]同t[i-j]~t[j]是否相等
15 void main(){
16 string s = "acabaabaabcacaabc";
17 string t = "abaabcac";
18 cout<<t<<"出現(xiàn)在"<<s<<"的第"<<indexOf(s,t,2)+1<<"位置。\n";
19 cout<<t<<"出現(xiàn)在"<<s<<"的第"<<indexOfKMP(s,t,2)+1<<"位置。\n";
20 system("pause");
21 }
22
23 int indexOf(string s,string t,int pos){//逐個字符匹配算法，從s串的pos位置開始,返回t出現(xiàn)的首位置
24 if(t.empty()){//字串不要為空
25 return -1;
26 }
27 int i = pos;
28 int temp = 0;
29 for(;i<s.size();i++){
30 temp = i;
31 for(int j = 0;j<t.size();j++){
32 if(s[temp] == t[j]){//如果相等,就繼續(xù)循環(huán)下去
33 temp++;
34 if(j == (t.size()-1)){
35 return i;//返回出現(xiàn)的首位置
36 }
37 }else{//不相等
38 break;
39 }
40 }
41 }
42 }
43 int indexOfKMP(string s,string t,int pos){//KMP算法；模式匹配的改進(jìn)算法；
44 if(t.empty()){//t字串不要為空
45 return -1;
46 }
47 int* next = new int[t.size()];
48 int pause = 0;//控制是否暫停的
49 getNext(t,next);
50 int i = 0,j = 0;
51 while(i!=s.size()){
52 if(s[i]==t[j]){
53 i++;
54 j++;
55 }else{
56 if(pause==1){//如果不需要暫停
57 pause=0;
58 i++;
59 }else{//如果需要暫停
60 pause=1;
61 }
62 j = next[j];
63 if(j==-1){
64 j=0;
65 }
66 }
67 if(j==t.size()){
68 return i-t.size();
69 }
70 }
71 return -1;
72 }
73 void getNext(string t,int* next){//求子字串t的next[]函數(shù)之并存入數(shù)組中
74 int temp = 0;
75 int zm = 0;
76 for(int i = 0; i < t.size();i++){//從0開始循環(huán)
77 temp = i-1;
78 if(i == 0){//第一個的時候，為-1
79 next[i] = -1;
80 }else if(temp > 0){
81 for(int j = temp;j>0;j--){
82 if(equals(t,i,j)){
83 next[i] = j;
84 break;
85 }else{
86 next[i] = 0;//視為其他情況為0
87 continue;
88 }
89
90 }
91 }else{
92 next[i] = 0;//其他情況為0
93 }
94
95 }
96
97 }
98 bool equals(string t,int i,int j){//比較字符串t[0]~t[j-1]同t[i-j]~t[j]是否相等
99 int temp = i-j;
100 //if((j-1)==(2*j-i)){//如果長度相同
101 for(int k = 0; k < j; k++,temp++){
102 if(t[k]!=t[temp]){//如果有不相同的，返回false
103 return false;
104 }
105 }
106 return true;//運(yùn)行到這兒說明字符串t[0]~t[j-1]同t[i-j]~t[j]相等
107 }
轉(zhuǎn)載于:https://www.cnblogs.com/silence250627170/archive/2011/07/25/2116666.html
總結(jié)
以上是生活随笔為你收集整理的KMP算法--字符串模式匹配算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
