bmhs.cpp

一种比较理想

//字符串匹配算法
//BMHS算法(BM算法的改进算法),区分大小写
//将BM算法的两种比较函数缩减为一种，并考虑下一字符

#include<stdio.h>
#include<stdlib.h>

#define pat_length 34  //模式字符串长度

int compare(unsigned char *t, unsigned char *p);
int skip_compare(int match);

unsigned char pat[pat_length+1]={"trial or increase the social benef"};  //存储模式数据，最后一位存储字符串终止符
unsigned char test[pat_length+1]={0};  //存储与模式等长的文本数据

void main()
{
	int i;
	int match;       //字符比较的返回值
	int skip;  //字符比较的返回值
	unsigned char *t,*p;   //分别指向test数组和pat数组

	FILE *fp;
	if((fp=fopen("e:/c projects/bmhs_algorithm/test.txt","r"))==NULL)  //打开文本文件
	{
		printf("Cannot open test file!");
		exit(1);
	}
	fread(test,sizeof(unsigned char),pat_length,fp);

	do
	{
		t=&test[pat_length-1];
		p=&pat[pat_length-1];

		match=compare(t,p);

		//如果字符串匹配则结束循环
		if(match==pat_length)
		{
			printf("Stream match!!!\n");
			break;
		}
		else  //否则分析当前已匹配字符的个数,并使文本数据左移相应个单元
		{
		    skip=skip_compare(match);
 
			//以下移动正文数据，并去掉换行符
			for(i=skip;i<pat_length;i++)
			test[i-skip]=test[i];
		    fread(&test[pat_length-skip],sizeof(unsigned char),skip,fp); 

		    for(i=pat_length-skip;i<pat_length;i++)   //如果中间存在换行符，则用空格符代替换行符
			{
				if(test[i]=='\n')  
				    test[i]=' ';
			}
		}
	}while(!feof(fp));

	if(match!=pat_length)
		printf("Stream not match......!!!\n");

	fclose(fp);
	return ;
}

//字符串比较函数，返回匹配字符的个数
int compare(unsigned char *t, unsigned char *p)
{
	int i;
	unsigned char a,d;
	for(i=0;i<pat_length;i++)
	{
		a=*t;
		d=*p;
//		printf("d=%c\n",d);
//		printf("a=%c\n",a);
		if(d==a)
		{
			t--;
			p--;
		}
		else
			break;
	}
	return i;  
}

int skip_compare(int match)
{
	int i;
	for(i=pat_length-match-2;i>0;i--)
	{
		if((pat[i]==test[pat_length-match-1])&&(pat[i-1]==test[pat_length-match-2]))
			return (pat_length-match-1-i);			
	}
	return (pat_length-match);
}