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