KMP算法

2023-06-09 20:22| 来源: 网络整理| 查看: 265

KMP算法是一种改进后的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。通过一个辅助函数实现跳过扫描不必要的目标串字符，以达到优化效果。

一般匹配字符串时，我们从目标字符串str（假设长度为n）的第一个下标选取和ptr长度（长度为m）一样的子字符串进行比较，如果一样，就返回开始处的下标值，不一样，选取str下一个下标，同样选取长度为n的字符串进行比较，直到str的末尾（实际比较时，下标移动到n-m）。这样的时间复杂度是O(n*m)。

KMP算法：可以实现复杂度为O(m+n)

为何简化了时间复杂度：充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量）。上面理不理解无所谓，我说的其实也没有深刻剖析里面的内部原因。

先不说kmp算法，先谈谈朴素的模式匹配算法。朴素的模式匹配算法是一种暴力匹配算法，也就是最蠢的匹配算法。如果失配的话，i,j都得变，i回溯至刚开头字符的下一位，j就置为0。这就造成了浪费，因为i已经回溯到刚才比较过了的字符，又需要再一次被比较，重复比较，造成浪费。如果i不动，只动j的话是不是可以呢。这就引出了kmp算法的精髓了。kmp算法就是保持i不动，通过修改j的位置，让模式串尽可能的移动到需要的地方。

“前缀”指除了最后一个字符以外，一个字符串的全部头部组合；

“后缀”指除了第一个字符以外，一个字符串的全部尾部组合；

废话少说，举个例子：”ababa” “部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABABA”为例，

－　“A”的前缀和后缀都为空集，共有元素的长度为0；

－　“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

－　“ABA”的前缀为[A, AB]，后缀为[BA, A]，共有元素为”A”，共有元素的长度1；

－　“ABAB”的前缀为[A, AB, ABA]，后缀为[BAB,AB, B]，共有元素为”AB”，共有元素的长度为2；

－　“ABABA”的前缀为[A, AB, ABA, ABAB]，后缀为[BABA, ABA, BA, A]，共有元素为”ABA”，长度为3；

KMP算法_字符串

也就是说next的值由部分匹配值整体向右移一位，且在第一位赋值-1后，再整体加1而成。

首先看看next数组值的求解方法例如：模式串 a b a a b c a c next值 0 1 1 2 2 3 1 2

next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。看起来很令人费解，利用上面的例子具体运算一遍。 1.前两位必定为0和1。 2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。 3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其next值对应的值与第三位的值相同。 4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。 5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。 6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。 7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。

void cal_next(char *str, int *next, int len) { next[0] = 0;//next[0]初始化为0，0表示不存在相同的最大前缀和最大后缀 int k = 0;//k初始化为0 for (int q = 1; q 0 && str[k] != str[q])//如果下一个不同，那么k就变成next[k]，注意next[k]是小于k的，无论k取任何值。 { k = next[k];//往前回溯 } if (str[k] == str[q])//如果相同，k++ { k = k + 1; } next[q] = k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q] } }#include #include void makeNext(const char P[],int next[]) { int q,k; int m = strlen(P); next[0] = 0; for (q = 1,k = 0; q < m; ++q) { while(k > 0 && P[q] != P[k]) k = next[k-1]; if (P[q] == P[k]) { k++; } next[q] = k; } } int kmp(const char T[],const char P[],int next[]) { int n,m; int i,q; n = strlen(T); m = strlen(P); makeNext(P,next); for (i = 0,q = 0; i < n; ++i) { while(q > 0 && P[q] != T[i]) q = next[q-1]; if (P[q] == T[i]) { q++; } if (q == m) { printf("Pattern occurs with shift:%d\n",(i-m+1)); } } } int main() { int i; int next[20]={0}; char T[] = "ababxbababcadfdsss"; char P[] = "abcdabd"; printf("%s\n",T); printf("%s\n",P ); // makeNext(P,next); kmp(T,P,next); for (i = 0; i < strlen(P); ++i) { printf("%d ",next[i]); } printf("\n"); return 0; }#include #include int next[100]; void getNextVal(char *pattern){ int k = -1; int j = 0; int len = strlen(pattern); next[j] = k; while(j < len){ if(k == -1 || pattern[j] == pattern[k]){ k++; j++; if(pattern[j] == pattern[k]) next[j] = next[k]; else next[j] = k; } else k = next[k]; } } int KMP_Searsh(char *str, char *pattern){ int i = 0; int j = 0; int slen = strlen(str); int plen = strlen(pattern); while(i < slen && j < plen){ if(j == -1 || str[i] == pattern[j]){ i++; j++; } else j = next[j]; } if(j == plen) return i - j; return -1; } int main() { int i; int ans; char str[] = {"abababaababacb"}; char pattern[] = {"ababacb"}; getNextVal(pattern); ans = KMP_Searsh(str, pattern); for(i = 0; i < strlen(pattern); i++) printf("%d ", next[i]); printf("\n"); if(ans != -1) printf("match! begin subscript: %d\n", ans); else printf("not match!\n"); return 0;

【本文地址】

公司简介

联系我们