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算法

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

本帖被以下淘专辑推荐:

评分

评分

评分