bmnew.cpp

BM 算法的VC实现

#include<iostream.h>
#define N 15

int k;
int n=15;
int m=8;

char t[]={' ','I', 'a','m', 'a', 's','t','u','d','e','n','t'};

char p[]={' ','s','t','u','d','e','n','t'};


int dist_t[N]; 

int flag=0;//标识位



void setdist()    //set dist_t[]
{

   for(int i=1;i<=n;i++)
       dist_t[i]=m;

   for( i=1;i<=n;i++)
   {
    
     for(int j=1;j<=m-1;j++)

     {
	   if(t[i]==p[j])
	      dist_t[i]=m-j;
	 
	 }//for

   }//for


}




void match()
{

int i=m;
int j;

 
  do{
     j=m;
	 k=i;

	 while((j>0)&&(p[j]==t[k]))
       {
	     j=j-1;
         k=k-1;
        }
    

     if(j==0)
	 {  
	    cout<<"matching is successful!";
        cout<<"position is :";
	   	cout<<i;
       i=i-m+1;
		flag=1;+1;
      }
	
     else
        
	  i=i+dist_t[i];

  }while (i>n||j==0);


   
}




int main(void)
{ 

   setdist();
   match();

   if(flag==0)

   cout<<"匹配失败";

   return 0;

}