当前位置: 首页> 财经> 金融 > 广东省江门开平疫情最新消息_站长统计入口_网站优化哪个公司好_太原seo培训

广东省江门开平疫情最新消息_站长统计入口_网站优化哪个公司好_太原seo培训

时间:2025/7/9 5:51:54来源:https://blog.csdn.net/2401_86190146/article/details/146428780 浏览次数:1次
广东省江门开平疫情最新消息_站长统计入口_网站优化哪个公司好_太原seo培训

KMP用于优化字符串匹配,通过先对模式串操作,然后在模式串和主串比较的时候就会减少那些不必要的比较

操作就是计算模式串的subnext[]数组,subnext[j] 表示的是前 j-1 位这个子串里面, 前k个字符和后k个字符相等,subnext[j] 保存的就是这个k的最大值

KMP未优化版

原理 

subnext[]创建

整体思路是借助j-1前面的值来计算第j位的subnext值

初始设置第0位的subnext值是-1,进入循环,使subnext[1]=0(第一位之前只有一位字符,首尾重复相同子串长度为0)

然后进入当j是普通的数的循环,如果第j位和第k位相同,说明在第j+1位的时候,前j位的k值为前j-1位的k减去1,如果sun[j]!=sun[k],此时需要回溯第k位的那个subnext值,让sub[j]和sub[subnext[k]]比较,如果相等就让subnext[j+1]的值是subnext[k]+1

因为此时在比较第j位和第subnext[k]位的时候,也满足字符串前subnext[k]位和后subnext[k]位是重复的,如果还是不相等就继续回溯,直到无法回溯为止(k==-1)

主串和模式串的比较

利用上个函数我们设计的subnext数组,就能减少比较的次数,假设主串检索到第i位,模式串检索到第j位,如果这时候它俩不一样,就从j跳转到subnext[j],因为这时候模式串的前subnext[j]位和后subnext[j]位字符是一样的,所以和主串的i-subnext[j]位字符也是一样的,就不用再比较了。如果pm或者ps有一个到头了,就停止比较

代码

#include<iostream>
#include<string>
using namespace std;
string m, sub;
int subnext[10000];
void creatnext()
{int j = 0; int k = -1;  //k表示在前j-1个字符里前后缀相等的字符有k个subnext[0] = -1;while (j < sub.length()-1)  //j表示在模式串遍历到的要求的那个next索引   由于最后一个字符与{if (k == -1 || sub[j] == sub[k])   //如果此时的k为负数要停止 避免越界访问//如果此时第j位等于第k位,说明继承k长度的首尾相同字符串成功{ j++;   //此时可以算出来下一位也就是subnext[j+1]的值为k+1 (因为sub[j] == sub[k]多了一位)k++;subnext[j] = k;}else k = subnext[k]; //不然就继续回溯}
}
int main()
{getline(cin, m);getline(cin, sub);int pm = 0, ps = 0;int lm = m.length();int ls = sub.length();creatnext();while (pm < lm && ps < ls)  {if (ps==-1 ||m[pm] == sub[ps]){pm++;ps++;}else ps = subnext[ps];}for (int i = 0; i < ls; i++)cout << subnext[i] << " ";cout << endl;if (ps == ls) cout << pm - ls;return 0;
}

KMP优化版

原理

大体原理和之前那个一样,优化的就是判断 sub[k] 和 sub[subnext[k]] 

假设子串 sub 为 "ABAB",传统next数组的构建过程如下:

索引0123
字符ABAB
next-1001

当 sub[3](字符 B)匹配失败时,根据 next[3] = 1,会回溯到 sub[1](字符 B)继续匹配。
但此时 sub[3] = B 和 sub[1] = B 字符相同,意味着即使回溯到 sub[1],下一步仍然会匹配失败(因为 sub[1] 与原位置字符相同)。

举个例子

匹配到主串的a和模式串的c不符合,然后模式串就跳到第二位的c了,但是这个c和之前的c是一样的,还是不匹配,所以就重复比较了

 

这个时候就加入了那个优化, 比较当前这个字符和要跳回去的那个字符是不是相等的,如果相等那就回溯到上上个字符

 if (sub[j] != sub[k]) {subnext[j] = k; } 
else subnext[j] = subnext[k]; 
void creatnext() {int j = 0;int k = -1;subnext[0] = -1;while (j < sub.length() - 1) { // 注意循环到j < len-1if (k == -1 || sub[j] == sub[k]) {j++;k++;// 优化next数组if (sub[j] != sub[k]) {subnext[j] = k; } else subnext[j] = subnext[k];  //直接回溯上上个} else k = subnext[k];    }
}

 

关键字:广东省江门开平疫情最新消息_站长统计入口_网站优化哪个公司好_太原seo培训

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: