montecarlo.cpp

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

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

unsigned long int I(char *s)//返回字符串的编码
{
	int len = strlen(s);
	unsigned long int result = 0;
	int flag = 1;

	for(int i=0;i<len;i++)
	{
		for(int j=1;j<len-i;j++)
			flag *= 10;
		result += (s[i])*flag;
		flag = 1;
	}
	return result;
}
/*void power(unsigned int a,unsigned int p,unsigned int n,unsigned int &result,bool &composite)
{
	unsigned int x;
	if(p == 0) 
		result = 1;
	else
	{
		power(a,p/2,n,x,composite);
		result = (x*x)%n;
		if((result == 1)&&(x!=1)&&(x!=n-1))
			composite = true;
		if((p%2)==1)
			result = (result*a)%n;
	}
}*/
int Prime(double M)
{ 	
	if(M>0 && M<250)
		return 241;
	else if(M<500)
		return 499;
	else if(M<1000)
		return 997;
	else if(M<5000)
		return 4999;
	else if(M<10000)
		return 9973;
	else 
		return 10013;
}

int MonteCarlo(char *x,char *y)//,int n,int m)
{
	int j = 1;
	int k;
	int n = strlen(x);
	int m = strlen(y);
	double M = 2*pow(n,2);
	int p = Prime(M);
	int *IpX = new int[n-m+1];
	int IpY = I(y) % p;
	int Wp = (int)pow(10,m+1) % p;
	char *ix = new char[m];
	
	for(int i=0;i<m;i++)
	{
		if(x[i] != '\0')
			ix[i] = x[i];
	}
	//ix[i] = '\0';

	IpX[0] = I(ix) % p;
	if(IpX[0] == IpY)
	{
		delete []ix;
		delete []IpX;
		return 0;
	}
	else if(m==n)
	{
		delete []ix;
		delete []IpX;
		return -1;
	}
	
	while(j<n-m+1)
	{
		k = 0;
		for(int i=j;i<j+m;i++)
		{	
			if(x[i] != '\0')
				ix[k] = x[i];
			k++;
		}
	//	ix[k] = '\0';
		IpX[j] = I(ix) % p;
		if(IpX[j] == IpY)
		{
			delete []ix;
			delete []IpX;
			return j;
		}
		else
			j++;
	}	
	delete []ix;
	delete []IpX;
	return -1;
}

void testMonteCarlo(char *a,char *b)
{
	int result;

	result = MonteCarlo(a,b);
//	cout<<"Pattern Matching:\n";
//	cout<<a<<endl<<b<<endl;
	if(result > -1)
	{
		cout<<"The MonteCarlo result is:"<<result<<endl;
		cout<<"After Matching:\n";
		cout<<a<<endl;
		for(int i=0;i<result;i++)
			cout<<" ";
		cout<<b<<endl;
	}
}