文章标题 原创 翻译 转载 文章内容 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。 ``` // 求子串nextval[]数组 // 如: // 元素编号 0 1 2 3 4 5 6 7 // 子串 a b a a b c a c // next值 -1 0 0 1 1 2 0 1 // nextval值 -1 0 -1 1 0 2 -1 1 // // 求next值,根据前一位(假如其字符为x)求后一位,如果字符x与其next值对应的字符相等则后一位在前一位的基础上加1。 // 如果不相等就根据next值继续往前找直到找到与字符x相等为止,那么就在找到的字符对应的next值基础上加1。 // 如果找到了next值为-1处还没找到,它的next值就为0. // 步骤如下: // 1>第0位必为-1; // 2>第1位必为0; // 3>第2位,前一位为b,next值为0,查看next值对应的字符为a,与它不相等所以为0; // 4>第3位,前一位为a,next值为0,查看next值对应的字符为a,与它相等所以1; // 5>第4位,前一位为a,next值为1,查看next值对应的字符为b,与它不相等,根据b的next值0继续往前找,找到了a与它相等, // 所以在b next值的基础上加1,即为1; // 6>第5位,前一位为b,next值为1,查看next值对应的字符为b,与它相等所以在b next值的基础上加1等于2; // 7>第6位,前一位为c,next值为2,查看next值对应的字符为a,与它不相等,继续查看a的next值0,编号0对应的字符为a还是不等, // 同时已到达-1的位置所以为0; // 8>第7位,前一位为a,next值为0,查看next值对应的字符为a,与它相等所以为1。 // // 根据next值求nextval值,当前字符与其next值对应的字符进行比较,不相等则为next值,相等则为next值字符对应的next值。 // 1>第0位必为-1; // 2>第1位字符为b,next值为0,与其next值对应的字符为a,不相等,为0; // 3>第2位字符为a,next值为0,与其next值对应的字符为a,相等,为-1; // 4>第3位字符为a,next值为1,与其next值对应的字符为b,不相等,为1; // 5>第4位字符为b,next值为1,与其next值对应的字符为b,相等,为0; // 6>第5位字符为c,next值为2,与其next值对应的字符为a,不相等,为2; // 7>第6位字符为a,next值为0,与其next值对应的字符为a,相等,为-1; // 8>第7位字符为c,next值为1,与其next值对应的字符为b,不相等,为1。 #include <assert.h> #include <iostream> using namespace std; void GetNextValue(const char *str, int * const next_value) { assert(str != NULL && next_value != NULL); int i = 0; int j = -1; int len = (int)strlen(str); next_value[i] = -1; while (i < len - 1) { if (j == -1 || str[i] == str[j]) { ++i; ++j; if (str[i] != str[j]) { next_value[i] = j; } else { next_value[i] = next_value[j]; } } else { j = next_value[j]; } } } // KMP算法求子串在父串里出现的位置(由0开始) int KmpSearch(const char *src, const char *dest, const int *next_value) { assert(src != NULL && dest != NULL && next_value != NULL); int i = 0; int j = 0; int src_len = (int)strlen(src); int dest_len = (int)strlen(dest); while (i < src_len && j < dest_len) { if (j == -1 || src[i] == dest[j]) { ++i; ++j; } else { j = next_value[j]; } } if (j >= dest_len) { return i - dest_len; } else { return -1; } } int _tmain(int argc, char *argv[]) { char src[] = "acabaabaabcacaabc"; char dest[] = "abaabcac"; const int count = sizeof(dest) / sizeof(dest[0]) - 1; int next_value[count] = {0}; GetNextValue(dest, next_value); int find_pos = KmpSearch(src, dest, next_value); cout << "find pos = " << find_pos << endl; cin.get(); return 0; } ``` 文章类别 Python Mobile Android Java Shell Life Database Bug Windows IOS Tools Boost Node.js Mac Product Tips C/C++ Golang Javascript React Qt MQ MongoDB Design Web Linux LLM ChatGPT RAG AI 提交