从KMP原理原理出发解决问题

本文主要是介绍从KMP原理原理出发解决问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

网上已经很多对具体过程的解释 我就不再赘述 这里 我只说一下 我对KMP算法的理解

ps:刚开始 也是想了好久 但是始终不得其解 后来 看了算法导论 然后想了想 就明白了

KMP算法原理

前提：next数组构造成功
如果匹配到pos位置匹配失败 那么在模式串中的匹配位置回跳到patten[0…pos-1]这个串的公共前后缀的下一个位置 这样就节省了匹配前缀的时间 KMP优化思想就在这里

next数组

void get_next(int lastPos)
{int i=1,j=0;next[0] = 0;next[1] = 0;while(i<=lastPos){if(patten[i]==patten[j]){if(j==0)next[i] = 0;i++;j++;next[i] = j;}else{if(j==0){next[i] = 0;i++;}elsej=next[j];}}
}

匹配算法

bool cast(int strLastPos,int pattenLen)
{int i=0;int j=0;while(i<=strLastPos){if(patten[j]==str[i]){i++;j++;}else{if(j==0)i++;elsej = next[j];}if(j==pattenLen)return true;}return false;} 

PS:如果看到这里 明白大致原理 但是还有那么一些模糊 推荐你去bilibili 去查 KMP算法 下面有一个汪看了也会懂的一个视频 讲解的非常透彻。
FINISHED！

更新时间2017.11.23

从书上发现了更精简的版本 然后自己写了一遍 orz

更新版

原先我们的next数组 到零了还得加一个if判断 更新版的next数组首元素是-1 所以就和匹配到相同的 做了合并，非常完美！ 顺便带上匹配函数（首匹配+返回匹配串的第一个字符下标）

#include<cstdio>
const int maxn = 1e7;
int next[maxn];
char p[maxn];
char s[maxn];
#include<cstring>void get_next(int ltp) 
{int i=1,j=0;next[0] = -1;while(i<=ltp){if(j==-1||p[i]==p[j]){i++;j++;next[i] = j;}   else{j = next[j];}}
}
int cast(int ltp,int plen)
{get_next(strlen(p)-1);int i=0,j=0;while(i<=ltp){if(j==-1||s[i]==p[j]){i++;j++;}else{j = next[j];}if(j==plen)return i-plen+1;}return -1;
}
int main()
{while(1){scanf("%s%s",p,s);printf("%d\n",cast(strlen(s)-1,strlen(p)));}return 0;
}

这篇关于从KMP原理原理出发解决问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---