kmpc语言
㈠ KMP c语言为什么要取Max{K}
#include <stdio.h>
int max (int a,int b);
main()
{
int x,y,z;
//int max(int a,int b);
printf("input two number:\n");
scanf("%d,%d",&x,&y);
z=max(x,y);
printf("maxnum=%d",z);
}
int max (int a,int b)
{
if (a>b)
return a;
else
return b;
}
㈡ 我这个c语言kmp的代码是否完善
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
voidgetnext(constchart[],intnext[])
{
inti=1,j=0,len2=strlen(t);
next[0]=-1;
next[i]=0;
while(i<len2)
{
if(j==0||t[i]==t[j])
{
++;j++;
next[i]=j;
}
elsej=next[j];
}
}
intkmp(constchars[],constchart[],constintnext[])
{
inti=0,j=0,len1=strlen(s),len2=strlen(t);
while(i<=len1&&j<len2)
{
if(j==-1||s[i]==t[j])
{
i++;j++;
}
elsej=next[j];
}
if(j>=len2)returni-len2+1;
elsereturn-1;
}
intmain()
{
intx,*next;
char*s,*t,buf[1000010];
while(1)
{
scanf("%s",buf);
x=strlen(buf);
s=(char*)malloc(sizeof(char)*(x+1));
strcpy(s,buf);
scanf("%s",buf);
x=strlen(buf);
t=(char*)malloc(sizeof(char)*(x+1));
strcpy(t,buf);
next=(int*)malloc(sizeof(int)*(x+1));
getnext(t,next);
x=kmp(s,t,next);
printf("%d ",x);
free(next);
free(s);
free(t);
}
return0;
}
㈢ 谁有KMP算法的C语言实现啊
|#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
void getNext(const char * t,int * Next)//get the Next array
{
int k=-1;
int j=0;
int size=strlen(t);
Next[0]=-1;
while(j<size)
{
if(k==-1||t[j]==t[k])//if k==-1 there are two conditions
//one is this is the first time entering the loop
{ //if t[j]==t[k] get the next[j+1] directly
k++;//the other is the end of the iteration cos k==-1;
j++;
Next[j]=k;//whatever Next[j]=k
}
else
k=Next[k];
}
}
int myStrstr(const char * Dest,const char *subStr)//find the starting position of the sub
{ //in the Dest through KMP
int destSize=strlen(Dest);
int subSize=strlen(subStr);
int i,j;
int * Next=(int *)(malloc(sizeof(int)*subSize));
i=j=0;
assert((Dest!=NULL)&&(subStr!=NULL));
getNext(subStr,Next);
while(i<destSize&&j<subSize)
{
if(j==-1||Dest[i]==subStr[j])//if j==-1 the main string need match the next elements
{ //and the subString begin from the beginning
i++; //if Dest[i]==subStr[j] both string need shift to the
j++; // next elements
}
else
j=Next[j]; //if match fail,glide back to Next[j]
}
if(j==subSize)return i-j;
return -1;
}
int main()
{
char *temp,*sub,* Dest;//to store the substring to be matched
int ch;
unsigned int templen,length=20*sizeof(char);
unsigned int mlength=20*sizeof(char);//the original length of the memory
sub=(char*)malloc(length);
Dest=(char*)malloc(length);
if(sub==NULL||Dest==NULL)//allocation failure
{
printf("memory allocate failure\n");
exit(0);
}
temp=sub;
printf("please input the substring:\n");
while((ch=getchar())!=10)//read the sub String
{
if((temp-sub)/sizeof(char)==length)//if running out of the memory
{
templen=length;
sub=realloc(sub,length+=20*sizeof(char));
if(sub==NULL)
{
printf("sub memory allocate failure\n");
exit(0);
}
temp=sub+templen*sizeof(char);//reset the temp cos the sub may change its value
}
*temp++=ch;
}
*temp='\0';
temp=Dest;
printf("please input the mainstring:\n");
while((ch=getchar())!=10)//read the main String
{
if((temp-Dest)/sizeof(char)==mlength)
{
templen=mlength;
Dest=realloc(Dest,mlength+=20*sizeof(char));//if running out of the memory
if(Dest==NULL)
{
printf("sub memory allocate failure\n");
exit(0);
}
temp=Dest+templen*sizeof(char);//reset the temp cos the Dest may change its value
}
*temp++=ch;
}
*temp='\0';
printf("the starting position is :%d\n",myStrstr(Dest,sub));//get the starting position
free(Dest);
free(sub);
return 0;
}
㈣ 关于KMP算法用数据结构C语言怎么实现
能说详细点吗，都不知道你为什么写不出来。
㈤ 求大神给一个KMP算法，C语言的
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void get_nextval(char const * ptn,int * nextval)
{
int i=0;
nextval[0]=-1;
int j=-1;
int plen=strlen(ptn);
if(ptn==NULL||nextval==NULL)
{
;
}
while(i<plen)
{
if(j==-1||ptn[i]==ptn[j])
{
++i;
++j;
if(ptn[i]!=ptn[j])
{
nextval[i]=j;
}
else
{
nextval[i]=nextval[j];
}
}
else
{
j=nextval[j];
}
}
}
int kmp_search(char const * src,char const * patn,int const * nextval,int pos)
{
int i=pos;
int j=0;
if(src==NULL||patn==NULL)
{
return -1;
}
int slen=strlen(src);
int plen=strlen(patn);
if(pos<0||pos>slen)
{
return -1;
}
while(i<slen && j<plen)
{
if(j==-1||src[i]==patn[j])
{
++i;
++j;
}
else
{
j=nextval[j];
}
}
if(j>=plen)
{
return i-plen;
}
else
{
return -1;
}
}
int main()
{
char src[]="";
char prn[]="abce";
int * nextval=(int *)malloc(sizeof(int)* strlen(prn));
get_nextval(prn,nextval);
int i=0;
for(i=0;i< strlen(prn);i++)
{
printf("%d",nextval[i]);
}
printf("\n");
printf("the result is:%d\n",kmp_search(src,prn,nextval,5));
return 0;
}
望点赞哦~~O(∩_∩)O~
㈥ 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 匹配算法，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算法是否正确，你自己再多去调试一下。
//另外就是，楼主最好注意编程风格问题，好的编程风格增强代码的可读性，也方便调试；这个最
//好是从一开始就坚持下去，久而久之你就会发现其中的好处了。
*****/
㈧ 串的KMP算法 c语言描述代码
这个网上很多啊
KMP算法的原理及实现【附C语言源码】回（原创）答http://apps.hi..com/share/detail/31073448
㈨ KMP算法的C语言程序
||#include "iostream"
#include "stdlib.h"
#include "stdio.h"
#include "malloc.h"
#define MAXSTRLEN 100
#define OK 1
#define NULL 0
using namespace std;
typedef char SString[MAXSTRLEN+1];
SString T,S;
int next[MAXSTRLEN],c[MAXSTRLEN];
int i,j;
void get_next(SString &T,int next[MAXSTRLEN]){
i=1;next[1]=0;j=0;
while(i<T[0]){
if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
}
int KMP(SString &S,SString &T){
i=1;j=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){++i;++j;}
else j=next[j];
}
if(j>T[0])return i-T[0];
else return 0;
}
void main(){
int k,p=1;
int i=1,j=1;
printf("输入主串：");
gets(&M[1]);
printf("输入模式串：");
gets(&N[1]);
while(M[i]!=NULL)
{
i++;
M[0]=i-1;
}
puts(&M[1]);
while(N[j]!=NULL)
{
j++;
N[0]=j-1;
}
puts(&N[1]);
if(M[0]>N[0])
{
printf("error!");
exit(0);
}
get_next(T,next);
for(i=1;i<=T[0];i++)printf("%d",next[i]);
printf("\n");
k=KMP(S,T);
printf("模式串从主串第%d个开始匹配！",k);
}
㈩ 请问数据结构c语言版kmp算法怎样实现c语言版的哦
没那么难，参版见权
http://blog.csdn.net/u013595419/article/details/50571792#t6