KMP算法求解next数组值(模式串从下标0开始或从下标1开始)以及求值后与主串的匹配过程

写在前面:博主是一位普普通通的19届二本大学生,平时最大的爱好就是听听歌,逛逛B站。博主很喜欢的一句话花开堪折直须折,莫待无花空折枝:博主的理解是头一次为人,就应该做自己想做的事,做自己不后悔的事,做自己以后不会留有遗憾的事,做自己觉得有意义的事,不浪费这大好的青春年华。博主写博客目的是记录所学到的知识并方便自己复习,在记录知识的同时获得部分浏览量,得到更多人的认可,满足小小的成就感,同时在写博客的途中结交更多志同道合的朋友,让自己在技术的路上并不孤单。

目录:
1.模式串从下标1开始的next数组求解
数据结构严蔚敏版
日常算法题版
2.模式串从下标0开始的next数组求解
模板1
模板2
3.模式串与主串的匹配
数据结构严蔚敏版
日常算法题版

1.模式串从下标1开始
1.1数据结构严蔚敏版

这个版本是官方标配版,第i个位置的next数组值的意义是:前i-1个字符的最大真公共前后缀的长度加1,加1的目的是下一次主串与模式串失配时模式串要跳到的位置。比如我们一个字符串abab那么它在此处的next数组值为0112;

void get_next(char T[],int next[])
{
int i=1;
int j=0;
next[1]=0;
while(i<T[0])//T[0]为字符串长度
{
if(j==0||T[i]==T[j])//T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
{
i++;
j++;
next[i]=j;
}
else
j=next[j];//若字符不相同那么j值回溯
}
}


1.1日常算法题版

有的时候,模式串需要我们手动的输入,我们可以选择从1开始输入字符串,然后求得此模式串的next数组值(注:kmp代表next数组),这个与严蔚敏版不同的是第i个位置的next数组值是前i个字符的最大真公共前后缀长度,比如字符串abab在此段代码中next数组值为0012

   cin>>str+1;//从数组下标为1开始输入
int len=strlen(str+1);
int j=0;
for(int i=2;i<=len;i++)
{
while(j>0&&str[j+1]!=str[i])
j=kmp[j];
if(str[j+1]==str[i])
j++;
kmp[i]=j;
}

2.模式串从下标0开始
2.1模板1

        kmp[0]=0;
int j=-1;
for(int i=1;i<needle.length();i++)
{
while(j>-1&&needle[j+1]!=needle[i])
{
if(j==0)//j==0的时候陷入死循环
{
j=-1;
break;
}
else
j=kmp[j]-1;
}
if(needle[i]==needle[j+1])
j++;
kmp[i]=j+1;
}

2.2模板2

        kmp[0] = 0;
int t;
for(int i = 1; i < s.length(); i++)
{
t = kmp[i-1];
while(t > 0 && s[i] != s[t])
t = kmp[t-1];
if(s[i] == s[t])
{
t++;
kmp[i] = t;
}
else
kmp[i]=0;
}

3.模式串与主串的匹配
3.1数据结构严蔚敏版

int Index_KMP(String S, String T, int pos){
// i 用于主串S当前位置下标值,若pos不为1,则从pos位置开始匹配
int i=pos;
//j 用于子串T中当前位置下标值
int j=1;
// 定义next数组
int next[255];

// 对串T作分析,得到next数组
get_next(T,next);

// 若i小于S的长度且j小于T的长度时,循环继续
while(i<=S[0] && j<=T[0]){
// 两字母相等则继续,相对于朴素算法增加了
// j=0 判断
if(j==0||S[i]==T[j]){
++i;
++j;
}
// 指针后退重新开始匹配
else{
// j退回合适的位置,i值不变
j=next[j];
}
}
if(j>T[0]){
return i-T[0];
}
else
return 0;
}

3.2算法题版(对应模式串从下标0开始的两个模板)

//haystack表示主串
//needle表示模式串
int i=0;
j=0;
int flag;
while(i<haystack.length())
{
flag=0;
if(haystack[i]==needle[j])
{
i++;
j++;
flag=1;
}
else
{
if(j>0)
{
j=kmp[j-1];
flag=1;
}
}
if(j==needle.length())
return i-needle.length();
if(flag==0)
i++;
}
return -1;

}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

KMP算法求解next数组值(模式串从下标0开始或从下标1开始)以及求值后与主串的匹配过程

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » KMP算法求解next数组值(模式串从下标0开始或从下标1开始)以及求值后与主串的匹配过程
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏