bm.cpp

著名的BM字符串匹配算法

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
#include <iostream.h>

char xx[50][80] ;
int maxline = 0 ;  /* 文章的总行数 */

int ReadDat(void)
{
  FILE *fp ;
  int i = 0 ;
  char *p ;

  if((fp = fopen("eng.in", "r")) == NULL) return 1 ;
  while(fgets(xx[i], 80, fp) != NULL) {
    p = strchr(xx[i], '\n') ;
    if(p) xx[i][p - xx[i]] = 0 ;
    i++ ;
  }
  maxline = i ;
  fclose(fp) ;
  return 0 ;
}

void PrintDat()
{
  FILE *fp ;
  int i ;

  fp = fopen("eng.out", "w") ;
  for(i = 0 ; i < maxline ; i++) {
    printf(" %s\n", xx[i]) ;
    //fprintf(fp, " %s\n", xx[i]) ;
  }
  fclose(fp) ;
}

int dist(char s[],int c)
{int num,i,result=0;
 num=strlen(s);
 for(i=0;i<num;i++)
 { if(s[i]==c)
 {if(i==num-1)result=num;
    else result=num-i-1;
	}
 }
 return result;
}
				 
int BM(char s[])
{int i,j,num,l,k,flag=0;
 
 for(l=0;l<maxline;l++)
 { num=strlen(s);
   i=num-1;
   //j=num-1;
   k=i; 
   while(xx[l][i])
   {k=num-1;
   //while(!isalpha(xx[l][i]))i++;
   j=i;
   while((i-j!=num)&&(xx[l][j]==s[k])){j--;   k--;}
   if(i-j==num)
   { cout<<"找到了：";
     cout<<l+1<<"行"<<"第"<<i-num+2<<"个字符开始。"<<endl;
	 i++; flag=1;
   }
   else if(i==j)i++;
        else {i=i+dist(s, s[k]);}
   }
 }
 return flag;
}
       
   



void main()
{ char s[80];
  int  dis=0,result; 
  if(ReadDat()) {
    printf("数据文件ENG.IN不能打开!\n\007") ;
    return ;
  }
  cout<<"                         BM算法"<<endl;
  cout<<"-------------------------------------------------------"<<endl;
  cout<<"读入的文章："<<endl;
  PrintDat() ;
  cout<<"-------------------------------------------------------"<<endl;
  cout<<"输入要查找的字符串：";
  cin>>s;
  result=BM(s);
  while(result==0)
  { cout<<"没有找到！！"<<endl;
    cout<<"输入要查找的字符串：";
    cin>>s;
    result=BM(s);
  }


}