c語言實現kmp演算法
⑴ 解析一哈c語言中的kmp演算法，bf演算法,kr演算法之間的聯系與區別，盡量淺顯易懂，謝謝！
三種演算法聯系：都是字元串匹配演算法。
區別：
「KMP演算法」：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指針i不變，將模式串的指針j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。
「BF演算法」是普通的模式匹配演算法，BF演算法的思想就是將目標串S的第一個字元與模式串P的第一個字元進行匹配，若相等，則繼續比較S的第二個字元和P的第二個字元；若不相等，則比較S的第二個字元和P的第一個字元，依次比較下去，直到得出最後的匹配結果。
「KR演算法」在每次比較時，用HASH演算法計算文本串和模式串的HASH映射，通過比較映射值的大小來比較字元串是否匹配。但是考慮到HASH沖突，所以在映射值相同的時候，還需要近一步比較字元串是否相同。但是在每次比較時，需要計算HASH值，所以選擇合適的HASH演算法很重要。
略知一二！
⑵ 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;
}
⑶ 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);
}
⑷ 數據結構中的KMP演算法怎樣用C實現
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define MAX_LEN_OF_STR 30 // 字元串的最大長度
typedef struct String // 這里需要的字元串數組,存放字元串及其長度{
char str[MAX_LEN_OF_STR]; // 字元數組
int length;// 字元串的實際長度
}String, *PString;
// 得到字元串的next數組
void GetNextArray(PString pstr, int next[])
{assert(NULL != pstr); <br/>assert(NULL != next);<br/>assert(pstr->length > 0);// 第一個字元的next值是-1,因為C中的數組是從0開始的<br/>next[0] = -1;<br/>for (int i = 0, j = -1; i < pstr->length - 1; )<br/>{// i是主串的游標,j是模式串的游標// 這里的主串和模式串都是同一個字元串<br/> if (-1 == j || // 如果模式串游標已經回退到第一個字元<br/>pstr->str[i] == pstr->str[j]) // 如果匹配成功<br/> {// 兩個游標都向前走一步<br/> ++i;++j;// 存放當前的next值為此時模式串的游標值<br/> next[i] = j;<br/> }else // 匹配不成功j就回退到上一個next值
{j = next[j];}}}
// KMP字元串模式匹配演算法
// 輸入: S是主串,T是模式串,pos是S中的起始位置
// 輸出: 如果匹配成功返回起始位置,否則返回-1
int KMP(PString S, PString T, int pos)
{assert(NULL != S);<br/> assert(NULL != T);<br/> assert(pos >= 0);<br/> assert(pos < S->length);<br/>if (S->length < T->length)<br/> return -1;<br/>printf("主串\t = %s\n", S->str);<br/>printf("模式串\t = %s\n", T->str);<br/>int *next = (int *)malloc(T->length * sizeof(int));// 得到模式串的next數組<br/>GetNextArray(T, next);<br/>int i, j;<br/>for (i = pos, j = 0; i < S->length && j < T->length; ){// i是主串游標,j是模式串游標<br/> if (-1 == j || // 模式串游標已經回退到第一個位置<br/> S->str[i] == T->str[j]) // 當前字元匹配成功<br/> {// 滿足以上兩種情況時兩個游標都要向前進一步<br/> ++i;++j;}
else // 匹配不成功,模式串游標回退到當前字元的next值
{j = next[j];}}
free(next);
if (j >= T->length)
{// 匹配成功
return i - T->length;}
else{// 匹配不成功
return -1;}}
⑸ 請會編程的同學幫忙用c語言寫一個無回溯模式匹配，kmp演算法。。
KMP演算法查亮拍納找串S中含串P的個數count #include <iostream> #include <stdlib.h> #include <vector> using namespace std; inline void NEXT(const string& T,vector<int>& next) { //按模式串生成vector,next(T.size()) next[0]=-1; for(int i=1;i<T.size();i++ ){ int j=next[i-1]; while(T[i]!=T[j+1]&& j>=0 ) j=next[j] ; /賀兆/遞推計算 if(T[i]==T[j+1])next[i]=j+1; else next[i]=0; // } } inline string::size_type COUNT_KMP(const string& S, const string& T) { //利用模式串T的next函數求T在主串S中的個數count的KMP演算法 //其中T非空， vector<int> next(T.size()); NEXT(T,next); string::size_type index,count=0; for(index=0;index<S.size();++index){ int pos=0; string::size_type iter=index; while(pos<T.size() && iter<敬沒S.size()){ if(S[iter]==T[pos]){ ++iter;++pos; } else{ if(pos==0)++iter; else pos=next[pos-1]+1; } }//while end if(pos==T.size()&&(iter-index)==T.size())++count; } //for end return count; } int main(int argc, char *argv[]) { string S=""; string T="ab"; string::size_type count=COUNT_KMP(S,T); cout<<count<<endl; system("PAUSE"); return 0; } 補上個Pascal的KMP演算法源碼 PROGRAM Impl_KMP; USES CRT; CONST MAX_STRLEN = 255; VAR next : array [ 1 .. MAX_STRLEN ] of integer; str_s, str_t : string; int_i : integer; Procere get_nexst( t : string ); Var j, k : integer; Begin j := 1; k := 0; while j < Length(t) do begin if ( k = 0 ) or ( t[j] = t[k] ) then begin j := j + 1; k := k + 1; next[j] := k; end else k := next[k]; end; End; Function index( s : string; t : string ) : integer; Var i, j : integer; Begin get_next(t); index := 0; i := 1; j := 1; while ( i <= Length(s) ) and ( j <= Length(t) ) do begin if ( j = 0 ) or ( s[i]= t[j] ) then begin i := i + 1; j := j + 1; end else j := next[j]; if j > Length(t) then index := i - Length(t); end; End; BEGIN ClrScr;{清屏，可不要} Write(『s = 』); Readln(str_s); Write(『t = 』); Readln(str_t); int_i := index( str_s, str_t ); if int_i <> 0 then begin Writeln( 'Found' , str_t,' in ', str_s, 'at ', int_i,' .' ); end else Writeln( 'Cannot find ', str_t,' in' , str_s, '. '); END.
⑹ 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演算法是否正確，你自己再多去調試一下。
//另外就是，樓主最好注意編程風格問題，好的編程風格增強代碼的可讀性，也方便調試；這個最
//好是從一開始就堅持下去，久而久之你就會發現其中的好處了。
*****/