bf.cpp

字符串匹配算法-BF算法

//字符串匹配算法
//BF(Brute Force)算法,区分大小写
#include<stdio.h>
#include<stdlib.h>

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

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

unsigned char pat[pat_length+1]={"consideration in Utah and Michigan"};  //存储模式数据，最后一位存储字符串终止符
unsigned char test[pat_length+1]={0};  //存储与模式等长的文本数据
void main()
{
	int i;
	int match;  //字符比较的返回值
	unsigned char *t,*p;   //分别指向test数组和pat数组

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

    do
	{
		t=test;
		p=pat;
		
		match=compare(t,p);
		//如果字符串匹配则结束循环
		if(match)
		{
			printf("Stream match!!!\n");
			break;
		}
		else   //否则向右滑行一个字符继续比较
		{
			for(i=0;i<pat_length-1;i++)
				test[i]=test[i+1];
		    fread(&test[pat_length-1],sizeof(unsigned char),1,fp); 

			if(test[pat_length-1]=='\n')  //如果最后一位是换行符，则用空格符代替换行符
				test[pat_length-1]=' ';
		}

	}while(!feof(fp));

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

	fclose(fp);
	return ;
}


//字符串比较函数，不匹配返回0,匹配返回1
int compare(unsigned char *t, unsigned char *p)
{
	int i;
	int match;
	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
		{
			match=0;
			break;
		}
	}
	if(i==pat_length)
		match=1;

	return match;  
}