首页 > 代码库 > KMP算法的基本实现,C++
KMP算法的基本实现,C++
KMP算法的实现,基于算法导论32.4节。
int* generateNext(string &p){ const int m = p.length(); int *next = new int[m]; int k = -1; next[0] = -1; for (int i = 1; i < m; i++) { while (k>-1 && p[k + 1] != p[i]) k = next[k]; if (p[k + 1] == p[i]) k++; next[i] = k; } return next;}void KMP_Matching(string&p, string&t){ const int m = p.length(); const int n = t.length(); int *next = generateNext(p); int k = -1; for (int i = 0; i < n; i++) { while (k>-1 && p[k + 1] != t[i]) k = next[k]; if (p[k + 1] == t[i]) k++; if (k == m - 1) { cout << "Found it at " << i - k << endl; k = next[k]; } }}
KMP算法的基本实现,C++
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。