lasvegas.cpp

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

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

int LasVegas(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)
		return 0;
	else if(m==n)
		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)
		{
			if(strcmp(ix,y)==0)
				return j;
		}
		else
			j++;
	}	
	delete []ix;
	delete []IpX;
	return -1;
}

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

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