凡科建站官网免费注册,网络架构中sdn是指,电影网站开发与设计,找券网站怎么做引言#xff1a;
在计算机科学中#xff0c;字符串匹配是一个常见的问题#xff0c;即在一个主串中查找一个模式串是否出现。朴素的字符串匹配算法需要对主串和模式串进行逐个字符的比较#xff0c;时间复杂度为O(m*n)#xff0c;其中m和n分别是主串和模式串的长度。然而…引言
在计算机科学中字符串匹配是一个常见的问题即在一个主串中查找一个模式串是否出现。朴素的字符串匹配算法需要对主串和模式串进行逐个字符的比较时间复杂度为O(m*n)其中m和n分别是主串和模式串的长度。然而当主串和模式串较长时这种暴力匹配算法的效率较低。
为了提高字符串匹配的效率KMPKnuth-Morris-Pratt算法应运而生。KMP算法通过构建一个next数组利用模式串的局部匹配信息来实现快速的字符串匹配。相比于朴素的暴力匹配算法KMP算法具有更高的效率时间复杂度为O(mn)。
本篇博客将介绍KMP算法的原理和实现方法。我们将详细解释next数组的求解过程并给出具体的实现代码。同时我们还将讨论KMP算法的应用领域和一些相关的扩展问题。
希望通过本篇博客的介绍你能够深入理解KMP算法并能够应用于实际问题中。让我们开始探索KMP算法的奥秘吧
BF算法
是普通的模式匹配算法BF算法的思想就是将目标串S的第一个字符与模式串T 的第一个字符进行匹配若相等则继续比较S的第二个字符和 T的第二个字符若不相等则比较S的第二个字符和 T的第一个字符依次比较下去直到得出最后的匹配结果。BF算法是一种蛮力算法。时间复杂度为O(m*n),一般不推荐使用。
假定我们给出字符串 ”ababcabcdabcde”作为主串 然后给出子串 ”abcd”,现在我们需要查找子串是否在主串中 出现出现返回主串中的第一个匹配的下标失败返回-1 ;
只要在匹配的过程当中匹配失败那么i回退到刚刚位置的下一个,j回退到0下标重新开始。 对应的代码模板如下
/* str:主串 sub:子串 */
int BF(char *str,char *sub) {
assert(str ! NULL sub ! NULL); if(str NULL || sub NULL) { return -1;
}int i 0; int j 0; int strLen strlen(str); int subLen strlen(sub); while(i strLen j subLen) { if(str[i] sub[j]) {i; j; } else {//回退 i i-j1; j 0; }
}if(j subLen){return i-j;}return -1;
}KMP算法
KMP算法的核心是利用匹配失败后的信息尽量减少模式串与主串的匹配次 数以达到快速匹配的目的。具体实现就是通过一个next()函数实现函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(mn) 。
区别KMP 和 BF 唯一不一样的地方在我主串的 i 并不会回退并且子串的 j 也不会移动到 0 号位置。
那么我的主串不回退我要怎么进行移动子串上的j来进行匹配呢
答案是移动j到当前字符串前缀和后缀相同的地方这样就避免了重复匹配的多余操作从而将O(m*n)的算法降为O(MN)的算法。我们用next数组来记录每次不匹配时j应该跳到的位置k。
而 K 的值是这样求的
1、规则找到匹配成功部分的两个相等的真子串不包含本身一个以下标 0 字符开始另一个以 j-1 下标
字符结尾。
2、不管什么数据 next[0] -1;next[1] 0;在这里我们以下标来开始而说到的第几个第几个是从 1 开始
求next数组的练习
练习 1 举例对于”ababcabcdabcde” 求其的 next 数组
-1 0 0 1 2 0 1 2 0 0 1 2 0 0
练习 2 再对”abcabcabcabcdabcde”,求其的 next 数组
-1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 0
接下来就是对于next[i1]?的求解从而得到一个普适公式
我们先假设next[i]k成立那么p[0]…p[k-1]p[x]…p[i-1]因为前缀和后缀的长度相等则xi-k。那么当p[k]p[i] 时next[i1]k1。 那么当p[k] ! p[i] 时那么k就要回退到next[k] 如果此时p[k]p[i],那么next[i1]k1,如果还是不等就要一直回退直到k0,如果p[0]p[i]那么next[i1]1如果还是不等next[i1]-110。 那么接下来来看代码
void GetNext(int *next,const char *sub){int lensub strlen(sub);next[0] -1;next[1] 0;int i 2;//下一项int k 0;//前一项的Kwhile(i lensub)//next数组还没有遍历完{if((k -1) || sub[k] sub[i-1])//{next[i] k1;i;k;//k k1???//下一个K的值新的K值}else{k next[k];}}
}
int KMP(const char *s,const char *sub,int pos)
{int i pos;int j 0;int lens strlen(s);int lensub strlen(sub);int *next (int *)malloc(lensub*sizeof(int));//和子串一样长assert(next ! NULL);GetNext(next,sub);while(i lens j lensub){if((j -1) || (s[i] sub[j])){i;j;}else{j next[j];}}free(next);if(j lensub){return i-j;}else{return -1;}
}结尾
在本篇博客中我们介绍了KMP算法的原理和实现方法。KMP算法通过构建next数组利用模式串的局部匹配信息来实现快速字符串匹配。相比于朴素的暴力匹配算法KMP算法具有更高的效率时间复杂度为O(mn)。
在KMP算法中next数组的求解是关键步骤。通过观察模式串的规律我们可以逐步求解出每个位置的next值从而实现指针的快速移动。通过实现一个KMP函数我们可以在主串中进行模式串的匹配找到第一个匹配的位置。
KMP算法的应用非常广泛例如在字符串匹配、文本搜索、DNA序列分析等领域都有广泛的应用。其核心思想和方法也可以用于其他问题的解决具有一定的普适性。
希望通过本篇博客的介绍你对KMP算法有了更深入的了解。如果你有任何问题或者想要了解更多相关内容欢迎留言交流。感谢阅读
