装修公司做网站推广能接到活吗,网站如何悬挂备案号,溧阳建设工程监理网站,常见的网站模式对kmp算法的理解中#xff0c;很重要的一点就是next数组。
很多人不理解next数组的含义#xff0c;是因为它同时具有两个意思#xff0c;而且这两个意思在不同的环境下不同。
现在给你两个字符串#xff1a;
一个是文本串 text
一个是模板串 pattern
然后定义两个指针…对kmp算法的理解中很重要的一点就是next数组。
很多人不理解next数组的含义是因为它同时具有两个意思而且这两个意思在不同的环境下不同。
现在给你两个字符串
一个是文本串 text
一个是模板串 pattern
然后定义两个指针指针i 指向文本串。指针 j 指向模板串。 现在我们要找模板串在文本串中第一次出现的位置。
那么直接从文本串的第一个字符和模板串的第一个字符开始匹配。itext[0] , jpattern[0])
如果ij匹配成功即 text[i] pattern[j] )
那么ij都往右移动。
如果i , j 匹配不成功那么我们希望 j能重新跳到模板串的某一个位置重新开始匹配。
这里不能让i跳因为 i的变化必须保持是线性的
如果我们能让 j 具备这样的功能的话那么匹配字符串将是线性复杂度。 那么我们就提出了一个next数组希望它能做到这件事。
不过要理解kmp
我们要搞清楚next数组有什么含义 如果i指针指向的字符 和 j指针指向的字符匹配失败j指针应该去的位置这里指的是j指针应该回到模板串的哪个下标next[k] 表示在模板串中从0开始到下标为k也就是[0,k]的字符串中最长相等前后缀的长度。 为什么这样说
其实我们一开始定义next数组的时候单纯的希望它有一个功能就是如果文本串和模板串发生不匹配那么指针j 去往的地方是 next[j-1] 。
(因为我们现在正在匹配 j 说明j-1 是已经匹配成功了的所
然后我们在求解 next数组的时候发现
next[k] 的值和 “在模板串中从0开始到下标为k的字符串中最长相等前后缀“ 的长度相等。
说明我们就可以通过这个特点来求解next数组。 什么意思呢 假设我们现在已经求好了next数组的值那么我们是不是可以根据next数组的含义如果i指针指向的字符 和 j指针指向的字符匹配失败j指针应该去的位置
来写出kmp主函数
int kmp(string text, string pattern) {//文本串模板串//分别表示文本串和模板串的长度int tlen text.size();int plen pattern.size(); vectorint nextget_next(pattern);//next数组//假设我们已经得到了next数组由于next数组的一个含义是当匹配失败模板串指针前往的位置//所以我们可以写出int j 0;for (int i 0; i tlen; i) { //遍历一遍文本串以线性的时间复杂度求出匹配位置if (pattern[j] text[i]) {//如果匹配了那么ji都往右边移动j;if (j plen) { //如果模板串全部都匹配上了return i - j;//直接返回第一次匹配成功的下标}}else {//如果没匹配上if (j 0) { //如果j大于0j next[j - 1]; //j前往应该去的地方}
//否则如果j等于0那么它无处可以去。}}return -1; //如果扫完了一遍文本串还没匹配直接返回-1
}很好根据next的数组的第一个含义我们能求出kmp函数。
但是我们怎么求next数组 只需要将next数组的性质结合起来即可。 在求next的数组中需要转变两种观点 当不匹配的时候把pattern[0,i]当作文本串、把patter[0,j] 看作模板串就按照上面kmp的步骤来即可。当不匹配直接让jnext[j-1] 当ij匹配 那么说明 [0,j-1]肯定是已经匹配上了的前提是j0)又[0,j-1]的长度是 j
现在j也匹配上了那么最长相等前后缀长度不就 j1 吗。
(也可以理解成如果 ij 匹配上了那么next[i]next[i-1]1、 因为匹配成功了一个新字符那么最长公共前后缀长度1
所以啊如果我们这样想的话那么next数组也求完了。 vectorint get_next(string pattern) { //求next数组并返回next数组int plen pattern.size();vectorint next(plen);int i 1, j 0; //此时我们将[0,i]当作文本串将[0,j]的串当作模板串for (int i 1; i plen; i) {while (j 0 and pattern[i] ! pattern[j]) { //如果不匹配那么j就退到应该去的直到退到0或者退到二者匹配j next[j];}if (pattern[i] pattern[j]) { //这里的话next就代表[0,i]区间的最长公共前后缀next[i] j;}}return next;}然后把二者合起来就是完整的板子了。
