DS\BF、BM、KMP算法

～风介～ · 发表于 2014-5-22 23:33:14

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由～风介～于 2014-5-23 16:37 编辑

先贴代码，晚一点出详解~ ^_^
BF算法比较简单上一张图：

#include<stdio.h>
#include<string.h>
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN];
int BF_Match(SString s,SString t)
{
int i=0,j=0;
int n=strlen(s),m=strlen(t);
while((i<n)&&(j<m))
{
if(s[i]==t[j]) /*匹配成功后，继续下一轮匹配，最后匹配成功后，i和j还要加一，然后跳出循环*/
{
i++;
j++;
}
else /*匹配失败，i回溯j置零，下一趟匹配*/
{
i = i-j+1;
j=0;
}
}
if(j==m)/*如果匹配成功的话，返回匹配成功的第一个位置*/
return (i-m);
else
return -1;
}
int main()
{
SString s,t;
int i;
printf("请输入主串s:");
scanf("%s",s);
printf("请输入模式串t:");
scanf("%s",t);
i = BF_Match(s,t);
if(i!= -1)
{
printf("模式串在主串中第一次出现的下标为:%d\n",i);
}
else
{
printf("主串中不存在模式串!\n");
}
return 0;
}

复制代码

BM算法

#include<stdio.h>
#include<string.h>
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN];
int BM(SString S,SString T)
{
int lenS,lenT,i,j;
lenS=strlen(S);
lenT=strlen(T);
for(i=0;i<=lenS-lenT;i++)/*当主串的字符小于模式串t时停止*/
{
if(T[0]==S[i]&&T[lenT-1]==S[i+lenT-1])/*比较第一个和最后一个字符*/
{
for(j=1;j<lenT-1;j++)/*比较*/
{
if(T[j]!=S[j+1])
break;
}
if(j==lenT-1) return i+1;
}
}
return 0;
}
int main()
{
int i;
SString S,T;
printf("请输入主串S:");
scanf("%s",S);
printf("请输入模式串T:");
scanf("%s",T);
i=BM(S,T);
if(i==0)
printf("主串中不存在模式串!\n");
else
printf("模式串在主串中第一次出现的下标为%d\n",i);
return 0;
}

复制代码

KMP算法

#include<stdio.h>
#include<string.h>
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN];
void get_next(SString T, int next[])
{
int lenT,i=1,j=0;
lenT=strlen(T);
next[1]=0;
while(i<lenT)
{
if(j==0 || T[i-1]==T[j-1])
{++i; ++j; next[i]=j;}
else
j=next[j];
}
printf("模式串T的next函数值为:");
for(i=1;i<=lenT;i++)
printf("%d ",next[i]);
printf("\n");
}
int KMP(SString S, SString T)
{
int next[MAXSTRLEN];
int lenS,lenT,i=1,j=1;
lenS=strlen(S);
lenT=strlen(T);
get_next(T,next);
while(i<=lenS && j<=lenT)
{
if(j==0 || S[i-1]==T[j-1])
{++i; ++j;}
else
j=next[j];
}
if(j>lenT) return i-lenT;
else return 0;
}
int main()
{
SString S,T;
int i;
printf("请输入主串S:");
scanf("%s",S);
printf("请输入模式串T:");
scanf("%s",T);
i=KMP(S,T);
if(i==0)
printf("主串中不存在模式串!\n");
else
printf("模式串在主串中第一次出现的下标为%d\n",i);
return 0;
}

复制代码

elvo · 发表于 2014-5-23 12:25:36

强烈支持楼主中。。。。
运行了BF算法程序，添加了一些注释和一小点修改：

#include<stdio.h>
#include<string.h>
#define MAXSTRLEN 255
//typedef unsigned char SString[MAXSTRLEN]; //mingw中报错：不能把‘unsigned char*’
//转换为'const char*' 所以修改如下：
typedef char SString[MAXSTRLEN] ;
/*************************************
/* BF *
**************************************/
int BF_Match(SString MainStr,SString PattStr)
{
int i=0,j=0;
int iMainStrLen=strlen(MainStr),iPattStrLen=strlen(PattStr); //取得字符串长度
while((i<iMainStrLen)&&(j<iPattStrLen))
{
if(MainStr[i]==PattStr[j]) /*最后匹配成功后，i和j还要加一，然后跳出循环*/
{
i++;
j++;
}
else /*匹配失败，i回溯，下一趟匹配*/
{
i = i-j+1;
j=0;
}
}
if(j==iPattStrLen) /*匹配成功*/
return (i-iPattStrLen);
else
return -1;
}
//----------------main func------------------
int main()
{
SString MainStr,PattStr;
int i;
printf("请输入主串MainStr:");
//scanf("%s",MainStr); //不能读空格
gets(MainStr);
printf("请输入模式串PattStr:");
//scanf("%s",PattStr);
gets(PattStr);
i = BF_Match(MainStr,PattStr); //调用BF匹配算法
if(i!= -1) //匹配成功
{
printf("模式串在主串中第一次出现的下标为:%d\n",i);
}
else
{
printf("主串中不存在模式串!\n");
}
return 0;
}

复制代码

elvo · 发表于 2014-5-23 12:58:39

强烈支持楼主。。。。
BM算法个人见解。。。。。修改了一下地方

#include<stdio.h>
#include<string.h>
#define MAXSTRLEN 255
///typedef unsigned char SString[MAXSTRLEN]; ///
typedef char SString[MAXSTRLEN];
int BM(SString MainStr,SString PattStr)
{
int iMainStrLen,iPattStrLen,i,j;
iMainStrLen=strlen(MainStr); //获取字符串长度
iPattStrLen=strlen(PattStr);
for(i=0;i<=iMainStrLen-iPattStrLen;i++)/*当主串的字符小于模式串t时停止*/
{
if(PattStr[0]==MainStr[i]&&PattStr[iPattStrLen-1]==MainStr[i+iPattStrLen-1])/*比较第一个和最后一个字符*/
{
//下面无法处理模式字符串PattStr的长度为1，如果iPattStrLen=1了
// 则不进入for循环，但是现在j=1
//下面的if判断语句则不能return（此时已经匹配成功的，但不能返回）
//于是在for循环后面加一句 if(iPattStrLen==1) return i;
for(j=1;j<iPattStrLen-1;j++)/*比较*/
{
//if(T[j]!=S[j+1]) /////////这里应该是j+i
if(PattStr[j]!=MainStr[j+i])
break;
}
if(iPattStrLen==1) return i;
if(j==iPattStrLen-1) return i; //匹配成功指示在主字符串中的下标，这里应该返回i而不是i+1吧
}
}
return 0;
}
//-------------main func--------
int main()
{
int i;
SString MainStr,PattStr;
printf("请输入主串MainStr:");
//scanf("%s",S);
gets(MainStr); //可以读取空格
printf("请输入模式串PattStr:");
//scanf("%s",T);
gets(PattStr);
i=BM(MainStr,PattStr);
if(i==0)
printf("主串中不存在模式串!\n");
else
printf("模式串在主串中第一次出现的下标为%d\n",i);
return 0;
}

复制代码

elvo · 发表于 2014-5-23 14:48:03

强烈支持楼主中。。。。
KMP这个。。。修改了一些地方，只是个人理解

#include<stdio.h>
#include<string.h>
#define MAXSTRLEN 255
//typedef unsigned char SString[MAXSTRLEN];
typedef char SString[MAXSTRLEN];
//---------GetNext-------------------------
/* KMP最核心的便是如何确定next数组，即模板字符串PattStr与
/* 主字符串MainStr不匹配时，下次该从何处开始匹配
/*比如模板字符串 PattStr=abchabcdaab
/*与主字符串匹配时当 PattStr[6]='c'与主字符串MainStr不匹配，
/*例如主字符串MainStr= ... abchabf...(省略号代码还有其他字符，只没有写出来)
/*发现主字符串中不匹配的'f'前的'ab'和开头ab一样，所以此时只需要匹配一下PattStr[2]与'f'是否匹配
/*而不用再从PattStr[0]匹配。如何知道主字符串如何与PattStr字符串的第3个字符比较呢？这就引进了next
/*数组，来存储这个PattStr的下标值。 ---额，上面说得不好 :-(
/*
/*******************************************
/*求next数组，举一个例子(用上面的例子)：
/* PattStr = abchabcdaab
/*则 next = -1,0,0,0,-1,0,0,3,-1,1,0
/* 这里要理解 PattStr[5]andPattStr[6]的next[5]!=1和next[6]！=2 以及 next[9]=1
/*比如主字符串 MainStr= ...abchabd... 当 PattStr[6]='c' 与主字符串相对应的'd'不匹配时
/*next[6]=2还是等于0呢？如果等于2，则用 PattStr[2]='c'继续与主字符串比较，但这明显重复运算了，所以此时next[6]=0
*/
void GetNext(SString PattStr, int next[])
{
int iPattStrLen,i=0,j=-1;
iPattStrLen=strlen(PattStr); //获得模式字符串的长度
next[0]=-1; //next[0]初始化为-1，任何串的第一个字符的模式值规定为-1。
while(i < iPattStrLen-1)
{
if(j==-1 || PattStr[i]==PattStr[j])
{
++i;
++j;
//下面4行修改了即是实现了上面的next[6]=0而不等于2的功能
if(PattStr[i] != PattStr[j])
next[i]=j;
else
next[i]=next[j];
}
else
j=next[j];
}
printf("模式串PattStr的next函数值为:");
for(i=0;i<=iPattStrLen-1;i++)
printf("%d ",next[i]);
printf("\n");
}
//-------------KMP----------
int KMP(SString MainStr, SString PattStr)
{
int next[MAXSTRLEN];
int iMainStrLen,iPattStrLen,i=0,j=0;
iMainStrLen=strlen(MainStr); //获得字符串长度
iPattStrLen=strlen(PattStr);
GetNext(PattStr,next); // 获得next数组
while(i < iMainStrLen && j < iPattStrLen)
{
if(j==-1 || MainStr[i]==PattStr[j])
{
++i;
++j;
}
else
j=next[j];
}
if(j>=iPattStrLen) return i-iPattStrLen; //匹配成功
else return 0;
}
//------------main func--------------
int main()
{
SString MainStr,PattStr;
int i;
printf("请输入主串MainStr:");
//scanf("%s",S);
gets(MainStr); //可以获得空格字符
printf("请输入模式串PattStr:");
//scanf("%s",T);
gets(PattStr);
i=KMP(MainStr,PattStr); //调用KMP
if(i==0)
printf("主串中不存在模式串!\n");
else
printf("模式串在主串中第一次出现的下标为%d\n",i);
return 0;
}

复制代码

O174 · 发表于 2014-6-12 22:15:47

学习一下~~

阿臣 · 发表于 2015-1-22 16:07:52

elvo 发表于 2014-5-23 12:58
强烈支持楼主。。。。
BM算法个人见解。。。。。修改了一下地方

对于单个字符就检测不到！\n

cuojue306 · 发表于 2015-1-23 01:39:15

看毛片算法还是有点难呀，学习下。

cuojue306 · 发表于 2015-1-23 01:39:54

支持下小甲鱼。

zjc7836 · 发表于 2015-1-24 09:31:52

学习一下

霜林尽染 · 发表于 2015-5-23 13:38:12

支持支持

骇客king · 发表于 2015-8-24 22:34:43

留着看看

y290176346 · 发表于 2015-9-23 20:10:39

我是来领鱼币的

waliemiao · 发表于 2015-10-7 16:13:43

cool

$DIM · 发表于 2015-10-25 14:14:55

对照算法实际应用，理解更快。

账号		自动登录	找回密码
密码			立即注册

[技术交流] DS\BF、BM、KMP算法

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分