昨天一天没有写出代码来,惭愧惭愧,昨天在看红黑树和堆排序,可惜最后都没有能写出东西来,渐渐的感觉网络上的中文资料不太可以依赖了啊,要么就是没有,要么就是 google 出来排名在前面的都会写错,看来要么转向英文资料,要么转向纸质书了
今天参考这里,http://blog.csdn.net/v_july_v/…,写了个 KMP 串匹配,感觉 KMP 也是网络上的中文资料好多错的,而且讲的也繁杂,看了好久都没有能够讲清楚
#include <iostream> #include <string> using namespace std; int kmp(const string &target, const string &pattern) { const int tar_len = target.size(); const int pat_len = pattern.size(); // 构造 next 数组 int *next = new int[pat_len]; next[0] = -1; int index = 0; for (int i=1; i<pat_len; i++) { index = next[i-1]; while (index>=0 && pattern[index+1]!=pattern[i]) { index = next[index]; } if (pattern[index+1] == pattern[i]) { next[i] = index + 1; } else { next[i] = -1; } } // KMP 匹配 int par_index = 0; int tar_index = 0; while (par_index<pat_len && tar_index<tar_len) { if (target[tar_index] == pattern[par_index]) { tar_index++; par_index++; } else if (par_index == 0) { tar_index++; } else { par_index = next[par_index-1] + 1; } } delete[] next; if(par_index == pat_len) { return tar_index-par_index; } else { return -1; } } int main() { string target = "ababc"; string pattern = "abc"; cout<<kmp(target, pattern)<<endl; return 0; }
输入输出
2