random.cpp

一种采用数学方法实现的字符串匹配算法-模式匹配的随机算法。

//字符串匹配算法
//随机模式匹配算法,区分大小写

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

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

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

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

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

	FILE *fp;
	if((fp=fopen("e:/c projects/random_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;
		pr=prime;
		
		match=compare(t,p,pr);
		//如果字符串匹配则结束循环
		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, unsigned char *pr)
{
	int i,k;
	unsigned char a,b,c;
	unsigned char BX,BY;

	for(k=0;k<5;k++)  //素数个数
	{
		t=test;
		p=pat;

		c=*pr;
	    BX=*t;
        BY=*p;
    	for(i=1;i<pat_length;i++)
		{
	    	a=*(++t);
	    	b=*(++p);

            BX=((BX*2)%c+a)%c;
	    	BY=((BY*2)%c+b)%c;
		}
//		printf("k=%d......\n",k);
    	if(BX!=BY)
		    return 0;
		else
			pr++;
	}
	return 1;
}