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