kmp算法代码C

❶ KMP算法中的nextval函数值的原理，求详细推导

1 get_nextval(int *nextval,const char *string)
2 {
3 int num=strlen(string);
4 int i=0,j=-1;
5 nextval[0]=-1;
6 while(i<num)
7 {
8 if(j==-1||string[i]=string[j])
9 {
10 i++;
11 j++;
12 if(string[i]==string[j])
13 {
14 nextval[i]=nextval[j];
15 }
16 else
17 {
18 nextval[i]=j;
19 }
20 }
21 else
22 {
23 j=next[j];
24 }
25 }
kmp的思想主要是通过nextval数组来指示“假如在子串与主串匹配过程中在某一位(假设为 j )匹配失败（不相等）时，子串应回到的位置。”以此区别于朴素模式匹配的一旦在某位匹配失败，就从头比较的特点。所以在生成与子串等长的nextval数组时，nextval数组每一个元素标识的就应该是当在子串的第j位与主串匹配失败时，应回到子串的哪一位。
设子串string为"abqabc"。主串为"abqabqabc"；生成nextval的思想是：假设目前 j 和 i 各处string的某一个位置，对比string[j]和string[i]（代码第8行），若相等，j 和 i 都向前一步，j , i 向前一步（代码10~11行）是为了下一次匹配，同时是为了在nextval[i]记录当子串与主串匹配失败时应回到子串的哪一位继续比较下去（代码第14或18行）。比如说当子串与主串在第六位（子串的c跟主串的q）匹配失败时，我们会希望nextval[5]记录的是2，这样"ab"就不需重新匹配。
可以看到在子串的 c 之前，"abqab" 是前缀(ab)与后缀(ab)相等的，有两位，所以在nextval[5]记录 2 ，意思就是当 c 与主串匹配失败时，直接回到子串string[2]继续比较即可。
在制作nextval数组的过程中，i只会往前，j如果遇到前缀string[j]不等于后缀string[i]时会回溯，往回找，看能不能找到与后缀相等的前缀。比如子串为"abqabac"，制作nextval数组时比较到第三位(q)跟第六位(a)时，此时q不等于a，所以j往回找，拿第二位（b）跟第六位（a）比较，还是不相等，继续往回找，找到一个位（a）跟第六位（a），相等，则在nextval[5]记录nextval[0]的值，即-1，这时如果子串跟主串的匹配在子串的第六位（a）匹配失败了，则直接略过主串的这一位，子串从头开始与主串的下一位继续进行匹配。

❷ C语言的KMP 匹配算法，VS老是报错，不知道是不是编译器的问题，请高手赐教啊！！！

//#include<iostream> //这一伍顷行是C++标准库，C语言编程时不需要
#include<stdio.h>
#include<string.h> //C语言字符串处理头文件是 string.h 而不是 string
//using namespace std; //这一行是C++标准命名空间的声明，C语言编程时不需要
#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

//计算最大滑动距离
void getnext(SString t,int next[])
{
int i,j;

////////////////////////////////////////////////////////////////////////////经典的KMP算法
i=0, j=-1; // 此处最好是分为两条语句，而不是写在一起，这也是编程风格问题
next[0] = -1;
while(i<t[0])
{
if(j==-1 || (j>=0 && t[i]==t[j]))
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
//*
//模式匹配，返回最小匹配的位置
int kmp(SString s, SString t,int next[])
{
int i = 0, j = 0;

while(i<s[0]&&j<t[0])
{
if(j==-1||s[i]==t[j])
{
++i,++j;
}
else j = next[j];
}
if(j>=t[0])
return i-t[0];
else return -1;
}
/////*/
int main()
{
int next[MAXSTRLEN];
SString s,t;
memset(s,0,sizeof(s));//对较大的数组进行初始化，有利于程序喊闷的多组数据测试，本例中只执行一
memset(t,0,sizeof(t)); //次程序，可暂时不需要，但是初始化以后更好，这个也属于编程风格问题
printf("please input a main string\n");
scanf("%s",s); // 楼主在此处应该小心，输入格式控制是 %s 而不是 s%
printf("please input a sub string\n");
scanf("%s",t); // 同上
getnext(t,next);
kmp(s,t,next);
return 0;
}
/****
//最后 此程序没有输出，不能看出来所需要的结果，因此不实用；不过前提要保证算法正确，我郑橘弯
//没有时间去验证你的这个KMP算法是否正确，你自己再多去调试一下。
//另外就是，楼主最好注意编程风格问题，好的编程风格增强代码的可读性，也方便调试；这个最
//好是从一开始就坚持下去，久而久之你就会发现其中的好处了。
*****/

❸ 串模式匹配算法（C语言）100分悬赏

第一个朴素算法:
1.普通的串模式匹配算法:
int index(char s[],char t[],int pos)
/*查找并返回模式串T在S中从POS开始的位置下标,若T不是S的子串.则返回-1.*/
{
int i,j,slen,tlen;
i=pos;j=0; //i,j分别指示主串和模式串的位置.
slen=strlen(s);tlen=strlen(t); //计算主串和模式串的长度.
while(i<slen && j<tlen)
{
if(s[i]==t[j]) {i++;j++;}
else {i=i-j+1;j=0;}
}
if(j>=tlen) return i-tlen;
return -1;
}

第二个KMP算法.该算法支持从主串的任意位置开始搜索.
2.KMP算法:
//求模式串的next函数.
void get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while(i<slen)
{
if(j==-1||p[i]==p[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}

//KMP模式匹配算法
int index_kmp(char *s,char *p,int pos,int next[])
/* 利用模式串P的NEXT函数,求P在主串S中从第POS个字符开始的位置*/
/*若匹配成功.则返回模式串在主串中的位置下标.否则返回-1 */
{
int i,j,slen,plen;
i=pos-1;j=-1;
slen=strlen(s);plen=strlen(p);
while(i<slen && j<plen)
{
if(j==-1||s[i]==p[j]) {++i;++j;}
else j=next[j];

❹ C语言数据结构中KMP算法编程中的问题

问题出在void StrCreate(Sqstring *s)这个函数中，
你在函数内给形参malloc内存，这些内存在函数返回时会被回收升租，因此相当于你没有分配内存。
解决的方法就是在main中分配内存，而不是在create中，或者也可以将create函返模数改一下：
Sqstring *StrCreate()
{
int i;
s=(Sqstring*)malloc(sizeof(Sqstring));
printf("请输入字符串(长度不吵世兆超过%d)!\n",Maxsize);
for(i=0;i<Maxsize;i++)
{
scanf("%c",s->data[i]);
if(s->data[i]=='1')
break;
}
s->length=i;
return s;
}
调用时先声明一个串指针
Sqstring *s;
s = StrCreate();
这样就可以了

❺ C语言KMP算法中的getnext函数,求详细解析！

刚调试完，看不懂再问吧，你贴的那个getnext不太直观，还是按书上的理解吧
#include<iostream>

using namespace std;

#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN];

int Index_KMP(SString S,SString T,int *next);
void Get_next(SString T,int *next);
void Input(SString *S);
void Display_next(SString T,int *next);
int main()
{
int next[10];
int pos;
int i=1,len=1;
SString S;
SString T;
// char P[200]="abc";
// char *q=P;
cout<<"Input moshi String:";
Input(&T);
cout<<"Input String:";
Input(&S);

// cout<<(int *)T<顷携谈<" "<<&T<<endl;
// cout<<(int)T[0];
// while((T[i++]=getchar())!='\n'雀碰);

// for(;T[len]!='\0';len++);
// cout<<len;
Get_next(T,next);
// Display_next(T,next);
pos=Index_KMP(S,T,next);
cout<<pos<<endl;
return 0;
}

void Display_next(SString T,int *next)
{
for(int i=1; i<(int)T[0];i++)
cout<<next[i];
}

void Input(SString *S)
{
int i=1;

while(((*S)[i++]=getchar())!='隐谈\n');
(*S)[i]='\0';
(*S)[0]=i-2;
// cout<<i;
}
void Get_next(SString T,int *next)
{
int i=1,j=0;
next[1]=0;
// cout<<(int)T[0];
while(i<(int)T[0])
{
//cout<<T[i]<<" "<<T[j]<<endl;
if(j==0||T[i]==T[j])
{
//cout<<next[i]<<endl;
i++,j++;
next[i]=j;

}
else
j=next[j];
}
}

int Index_KMP(SString S,SString T,int *next)
{
int i=1,j=1;
while(i<=(int)S[0]&&j<=(int)T[0])
{
if(j==0||S[i]==T[j])
{
i++,j++;
}
else
j=next[j];
}
if(j>(int)T[0])
return i-(int)T[0];
else
return 0;
}