DS\BF、BM、KMP算法,数据结构与算法,编程语言专区,鱼C论坛

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

DS\BF、BM、KMP算法

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

先贴代码，晚一点出详解~ ^_^
BF算法比较简单上一张图：
#include<stdio.h>
#include<string.h>
#define MAXSTRLEN 255
typedef unsigned char SString;
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==t) /*匹配成功后，继续下一轮匹配，最后匹配成功后，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;
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==S&&T==S)/*比较第一个和最后一个字符*/
{
for(j=1;j<lenT-1;j++)/*比较*/
{
if(T!=S)
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;
void get_next(SString T, int next[])
{
int lenT,i=1,j=0;
lenT=strlen(T);
next=0;
while(i<lenT)
{
if(j==0 || T==T)
{++i; ++j; next=j;}
else
j=next;
}
printf("模式串T的next函数值为:");
for(i=1;i<=lenT;i++)
printf("%d ",next);
printf("\n");
}
int KMP(SString S, SString T)
{
int next;
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==T)
{++i; ++j;}
else
j=next;
}
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;//mingw中报错：不能把‘unsigned char*’
                                                                                    //转换为'const char*'所以修改如下：
typedef char SString    ;

/*************************************
/*    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==PattStr) /*最后匹配成功后，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;///
typedef char SString;

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==MainStr&&PattStr==MainStr)/*比较第一个和最后一个字符*/
{

//下面无法处理模式字符串PattStr的长度为1，如果iPattStrLen=1了
// 则不进入for循环，但是现在j=1
//下面的if判断语句则不能return（此时已经匹配成功的，但不能返回）
//于是在for循环后面加一句 if(iPattStrLen==1) return i;
   for(j=1;j<iPattStrLen-1;j++)/*比较*/
   {
//if(T!=S)/////////这里应该是j+i
if(PattStr!=MainStr)
      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;
typedef char SString;

//---------GetNext-------------------------
/* KMP最核心的便是如何确定next数组，即模板字符串PattStr与
/* 主字符串MainStr不匹配时，下次该从何处开始匹配
/*比如模板字符串PattStr=abchabcdaab
/*与主字符串匹配时当 PattStr='c'与主字符串MainStr不匹配，
/*例如主字符串MainStr= ... abchabf...(省略号代码还有其他字符，只没有写出来)
/*发现主字符串中不匹配的'f'前的'ab'和开头ab一样，所以此时只需要匹配一下PattStr与'f'是否匹配
/*而不用再从PattStr匹配。如何知道主字符串如何与PattStr字符串的第3个字符比较呢？这就引进了next
/*数组，来存储这个PattStr的下标值。 ---额，上面说得不好 :-(
/*
/*******************************************
/*求next数组，举一个例子(用上面的例子)：
/* PattStr = abchabcdaab
/*则 next = -1,0,0,0,-1,0,0,3,-1,1,0
/* 这里要理解 PattStrandPattStr的next!=1和next！=2 以及 next=1
/*比如主字符串MainStr= ...abchabd...当 PattStr='c' 与主字符串相对应的'd'不匹配时
/*next=2还是等于0呢？如果等于2，则用 PattStr='c'继续与主字符串比较，但这明显重复运算了，所以此时next=0
*/
void GetNext(SString PattStr, int next[])
{
int iPattStrLen,i=0,j=-1;
iPattStrLen=strlen(PattStr);//获得模式字符串的长度
next=-1; //next初始化为-1，任何串的第一个字符的模式值规定为-1。

while(i < iPattStrLen-1)
{
if(j==-1 || PattStr==PattStr)
{
++i;
++j;
//下面4行修改了即是实现了上面的next=0而不等于2的功能
if(PattStr != PattStr)
next=j;
else
next=next;
}
else
   j=next;
}

printf("模式串PattStr的next函数值为:");
for(i=0;i<=iPattStrLen-1;i++)
printf("%d ",next);
printf("\n");
}

//-------------KMP----------
int KMP(SString MainStr, SString PattStr)
{
int next;
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==PattStr)
{
++i;
++j;
}
else
   j=next;
}
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

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

页: [1]

鱼C论坛's Archiver

DS\BF、BM、KMP算法