KMP模板

KMP模板

KMP算法要解决的问题就是在substring在string中的匹配。如果子串在给定字符串中出现，则返回出现的具体位置，否则返回-1。

正常的思路是在给定的字符串遍历中嵌套子串的遍历，如果匹配成功返回具体位置，否则返回-1。 有以下代码：

#include #include #include #include #include using namespace std;int func(string str, string substr){ int i=0, j=0; while (i>str>>substr; printf("%d", func(str, substr)); return 0;}

或者是这样的：

#include#includeint max=0,start;void hhh(char *str1,char *str2){ int i,j,num=0,strlen1,strlen2; strlen1=strlen(str1); strlen2=strlen(str1); for(i=0;imax) { max=num; start=i; } num=0; } }}int main(){ int i; char str1[1000],str2[1000]; gets(str1); gets(str2); hhh(str1,str2); printf("Length of String1: %d\nLength of String2: %d\n",strlen(str1),strlen(str2)); printf("Maxsubstring:"); for(i=0;i

但是如果在总字符串中的某一个位置开始，和子串很多个字符都匹配后有一个又不匹配了，那么在总字符串中还要回到那个位置的下一个位置，这样就造成了浪费。为了解决这个问题，下面是KMP算法

KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组。里面存储的是一个字符串的前缀集合和后缀集合中相同子串的最大的长度，如果用这个数组存子串的信息，那么在总串的i位置开始后匹配了j个字符，第j+1个字符不匹配，那么至少可以保证总串i到i+j-1的位置和子串的0到j-1的字符段相同，这时子串这段的TMP表示这段中有几个字符既可以做子串的前缀又可以做它的后缀。由于子串的后缀的这几个字符一定和总串一样，那么总串的这个位置的字符段就可以做为子串的前缀。因此，如果某个位置匹配失败后，i在总串的位置不用移动，只是移动j在子串的位置就好。

下面是KMP算法模板 具体的代码怎么来的我也不太懂…

#include #include #include #include #include using namespace std;void get_next(string s, int next[]){//next存储前n个字符段的前后缀相同的最大长度 int i=0, j=-1; next[0]=-1;//为达到next的存储规则，整体向右偏移一位，[0]位置-1标记 int len=s.length(); while (i>str>>substr; printf("%d", kmp(str, substr)); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。