首页 > 代码库 > 算法之美--3.2.3 KMP算法
算法之美--3.2.3 KMP算法
不知道看了几遍的kmp,反正到现在都没有弄清楚next[j]的计算和kmp的代码实现,温故而知新,经常回来看看,相信慢慢的就回了
1 /*! 2 * \file KMP_算法.cpp 3 * 4 * \author ranjiewen 5 * \date 2017/02/12 16:12 6 * 7 */ 8 9 void preKmp(const char* pattern, int m, int kmpNext[]) 10 { 11 int i, j; 12 i = 0; 13 j = kmpNext[0] = -1; 14 while (i<m) 15 { 16 while (j>-1&&pattern[i]!=pattern[j]) 17 { 18 j = kmpNext[j]; 19 } 20 i++; 21 j++; 22 if (pattern[i]==pattern[j]) 23 { 24 kmpNext[i] = kmpNext[j]; 25 } 26 else 27 { 28 kmpNext[i] = j; 29 } 30 } 31 } 32 33 #include <iostream> 34 using namespace std; 35 #include <string> 36 37 void KMP(string p, string t) 38 { 39 int m = p.length(); 40 int n = t.length(); 41 if (m>n) 42 { 43 cerr << "Unsuccessful match!"; 44 } 45 const char* x = p.c_str(); 46 const char* y = t.c_str(); 47 48 int i = 0, j = 0, kmpNext[128]; 49 preKmp(x, m, kmpNext); 50 51 i = j = 0; 52 while (i<n) 53 { 54 while (j>-1&&x[j]!=y[i]) 55 { 56 j = kmpNext[j]; 57 } 58 j++; 59 i++; 60 if (j>=m) 61 { 62 cout << "Matching index found at:" << i - j << endl; 63 j = kmpNext[j]; 64 } 65 } 66 } 67 68 int main(int argc, char** argv) { 69 70 string p1 = "abcabcad"; 71 string p2 = "adcadcad"; 72 string p3 = "ababcaabc"; 73 string t = "ctcabcabcadtcaabcabcadat"; 74 75 cout << "KMP: " << endl; 76 KMP(p1, t); 77 78 // cout<<"KMP: "<<endl; 79 // KMP(p2, t); 80 81 // cout<<"KMP: "; 82 // KMP(p3, t); 83 84 return 0; 85 }
算法之美--3.2.3 KMP算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。