从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;
}