main.cpp

这是计算机专业硕士生课程《算法设计与实现》中讲到的模式匹配算法的实现

#include<iostream.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#include"interface.h"

//#define charRang (127-33)

void RandStr(char *a,char *b,int aLen,int bLen)
{
	time_t t;
	srand((unsigned)time(&t));

	int random;
	for(int i=0;i<aLen;i++)
	{
		random = rand();
		if(random>'A' && random<'Z' || random>'a' && random<'z')
			a[i] = (random);
		else 
			if(random>'Z'&&random<'a')
				a[i] = (char)('A'+random%26);
			else
				a[i] = (char)('a'+random%26);
	}
    a[i] = '\0';
	for(i=0;i<bLen;i++)
	{
		random = rand();
		if(random>'A' && random<'Z' || random>'a' && random<'z')
			b[i] = (random);
		else 
			if(random>'Z'&&random<'a')
				b[i] = (char)('A'+random%26);
			else
				b[i] = (char)('a'+random%26);
	}
	b[i] = '\0';
}

void main()
{
	int     i;
	char   *a;
	char   *b;
	int     aLen;
	int     bLen;
	int     total_time1,total_time2,total_time3;
	clock_t start,end1,end2,end3;
	time_t  t;

	srand((unsigned)time(&t));

		total_time1 = 0;
		total_time2 = 0;
		total_time3 = 0;
	//	start = clock();
		for(i=0;i<5000;i++)
		{
			aLen = rand()%50+1;
			bLen = aLen - rand()%aLen;
			a = new char[aLen+1];
			b = new char[bLen+1];

			RandStr(a,b,aLen,bLen);
		start = clock();
				testKMP(a,b);
	end1=clock();
				testMonteCarlo(a,b);
					end2=clock();
				testLasVegas(a,b);
					end3=clock();

			total_time1 += (end1-start);
			total_time2 += (end2-end1);
			total_time3 += (end3-end2);
			delete []a;
			delete []b;
		}
		cout<<"The KMP run time is :"<<total_time1<<endl;
		cout<<"The MentoCarlo run time is :"<<total_time2<<endl;
		cout<<"The LasVegas run time is :"<<total_time3<<endl;
}