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算法是否正确，你自己再多去调试一下。
//另外就是，楼主最好注意编程风格问题，好的编程风格增强代码的可读性，也方便调试；这个最
//好是从一开始就坚持下去，久而久之你就会发现其中的好处了。
*****/