bm.cpp

一种比较理想

//字符串匹配算法
//BM(Boyer Moore)算法,区分大小写

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

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

int compare(unsigned char *t, unsigned char *p);
int shift_compare(int match);
int skip_compare(int match);
int sub_stream1(int location, int length);  //分析匹配子串的子函数
int sub_stream2(int location); 
int max_shift(int shift,int skip);

unsigned char pat[pat_length+1]={"consideration in Utah and Michigan"};  //存储模式数据，最后一位存储字符串终止符
unsigned char test[pat_length+1]={0};  //存储与模式等长的文本数据

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

	FILE *fp;
	if((fp=fopen("e:/c projects/bm_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  //否则分析当前已匹配字符的个数,并使文本数据左移相应个单元
		{
		    shift=shift_compare(match);
		    skip=skip_compare(match);
			max=max_shift(shift,skip);
 
			//以下移动正文数据，并去掉换行符
			for(i=max;i<pat_length;i++)
			test[i-max]=test[i];
		    fread(&test[pat_length-max],sizeof(unsigned char),max,fp); 

		    for(i=pat_length-max;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 shift_compare(int match)
{
	int i,j;
	int tr1,tr2;  //判断是否全部匹配或前缀匹配
	int sub_length=0;  //真子串长度

	if(match==0)  //表示已匹配字符个数为0
		sub_length=1;    //正文左移一位
	else
	{
		for(i=pat_length-2;i>=0;i--)
		{
			if(pat[pat_length-1]==pat[i])
			{
				tr1=sub_stream1(i,match);
				if(tr1==1&&(pat[pat_length-1-i-match]!=pat[pat_length-1-match]))  //全部匹配
				{
					sub_length=(pat_length-1-i);   //正文左移i位
					break;
				}
				else    
				{
					for(j=match-1;j>=0;j--)
					{
						if(pat[pat_length-1]==pat[j])
						{
							tr2=sub_stream2(j);
							if(tr2)            //前缀匹配
							{
				            	sub_length=(pat_length-1-j);   //正文左移i位
								break;
							}
						}
					}
				}
			}
		}
		if(i==pat_length)  //表示没有匹配子串
			sub_length=pat_length;
	}

	return sub_length;
}


//分析已匹配部分是否再次出现的子函数
//存在返回1，否则返回0
int sub_stream1(int location, int length)  //shift的第一种情况
{
	int k,t;
//	printf("length=%d\n",length);
	for(k=(pat_length-1),t=location; k>(pat_length-length-1),t>location-length; k--,t--)
	{
		if(pat[t]!=pat[k])
			return 0;
//		printf("pat[%d]=%c\n",t,pat[t]);
	}
//    printf("匹配部分再次出现.......\n");
    return 1;
}

int sub_stream2(int location)   //shift的第二种情况
{
	int k,t;
	for(k=(pat_length-1),t=location; k>=(pat_length-location-1),t>=0; k--,t--)
	{
		if(pat[t]!=pat[k])
			return 0;
	}
//    printf("前缀匹配.......\n");
    return 1;
}

//坏字符移动函数,返回需移动的长度
int skip_compare(int match)
{
	int i;
	for(i=pat_length-match-2;i>=0;i--)
	{
		if(pat[i]==test[pat_length-match-1])
			return (pat_length-match-1-i);			
	}
	return (pat_length-match);
}

int max_shift(int shift,int skip)
{
	if(skip>shift)
		return skip;
	else
		return shift;
}