matching.cpp

Las Vegas

// matching.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdlib.h"
#include <stdio.h>
#include "Windows.h"
#include <time.h>
#include <math.h>
#include <iostream.h>

#define MATCH_T 10
#define MATCH_TIMES 500
#define MATCH_LENGTH 1000
#define PATTERN_LENGTH 80

long M=2*PATTERN_LENGTH*PATTERN_LENGTH;
long prime[100];//小于Ｍ且最接近的１００的素数
long Prime;
long Prime2;
void primeGen(long max)
{  
  bool done=false;
  long temp=max;
  for(int i=0;i<100;i++)
  {   
	  done =false;
	  while(!done)
		  {
		  for(long j=2;j<=sqrt(temp);j++)
			  {
			  if(temp%j==0)
				  break;
			  }
		  if(j>sqrt(temp))
		  {
			  done=true;
			  prime[i]=temp;
		  }
		  temp=temp--;
	  }
  }

}

long ComputeSpan(LPSYSTEMTIME BeforeTime, LPSYSTEMTIME AfterTime)
{
	long lbTime, laTime;
	lbTime = BeforeTime->wMilliseconds + BeforeTime->wSecond * 1000 + BeforeTime->wMinute * 60000;
	laTime = AfterTime->wMilliseconds + AfterTime->wSecond * 1000 + AfterTime->wMinute * 60000;
	return laTime - lbTime;
}

void RandString(char* strX, char* strY, int& xLen, int& yLen)
{
	xLen = (rand() % MATCH_LENGTH) / 2 + MATCH_LENGTH / 2;
	yLen = rand() % PATTERN_LENGTH + 1;

    
	//生成随机01字符串
	for(int i = 0; i < xLen; i++)
	{
		if(rand() > RAND_MAX / 2)
			strX[i] = '1';
		else
			strX[i] = '0';
	}

	for(int j = 0; j < yLen; j++)
	{
		if(rand() > RAND_MAX / 2)
			strY[j] = '1';
		else
			strY[j] = '0';
	}
}


bool KMPMatch(const char* strX, const char* strY, int xLen, int yLen)
{
	int PatternFail[PATTERN_LENGTH];
	//计算失败函数
	PatternFail[0] = -1;
	for(int i = 1; i < yLen; i++)
	{
		int j = PatternFail[i - 1];
		while((*(strY + i) != *(strY + j + 1)) && (j >= 0))
			j = PatternFail[j];
		if(*(strY + i) == *(strY + j + 1))
			PatternFail[i] = j + 1;
		else
			PatternFail[i] = -1;
	}

	//进行字符串匹配比较
	int posX = 0, posY = 0;
	while(posX < xLen && posY < yLen)
	{
		if(strX[posX] == strY[posY])
		{
			posX++;
			posY++;
		}
		else if(posY == 0)
			posX++;
		else
			posY = PatternFail[posY - 1] + 1;
	}
	if(posY < yLen)
		return false;
	else
		return true;
}

bool MonteCarloMatch1(const char* strX, const char* strY, int xLen, int yLen)
{
     long lpX = 0, lpY = 0, wp = 1;
	//取素数
	//计算Y串的指纹,计算X(1)的指纹,计算Wp
	for(int i = 0; i < yLen; i++)
	{
		lpY = (lpY * 2 + (strY[i] - '0')) % Prime;
		lpX = (lpX * 2 + (strX[i] - '0')) % Prime;
		wp = (wp * 2) % Prime;
		
	}
	
	int j = 0;
	while(j <= xLen - yLen)
	{
		if(lpY == lpX )
			return true;
		else if(j == xLen - yLen)
			return false;
		else
		{
			lpX = lpX * 2 - wp * (strX[j] - '0') + (strX[j + yLen] - '0');
			if(lpX < 0)
				lpX += Prime;
		    else
				lpX %= Prime;
			j++;
		}
	}
	return false;
}

bool MonteCarloMatch2(const char* strX, const char* strY, int xLen, int yLen)
{
	long lpX1 = 0,lpX2 = 0, lpY1 = 0,lpY2 = 0, wp1 = 1,wp2 =1; 
	//取素数
	//计算Y串的指纹,计算X(1)的指纹,计算Wp
	for(int i = 0; i < yLen; i++)
	{
		lpY1 = (lpY1 * 2 + (strY[i] - '0')) % Prime;
		lpX1 = (lpX1 * 2 + (strX[i] - '0')) % Prime;
		wp1 = (wp1 * 2) % Prime;
		
		lpY2 = (lpY2 * 2 + (strY[i] - '0')) % Prime2;
		lpX2 = (lpX2 * 2 + (strX[i] - '0')) % Prime2;
		wp2 = (wp2 * 2) % Prime2;

	}
	
	int j = 0;
	while(j <= xLen - yLen)
	{
		if((lpY1 == lpX1) && (lpY2 == lpX2))
			return true;
		else if(j == xLen - yLen)
			return false;
		else
		{
			lpX1 = lpX1 * 2 - wp1 * (strX[j] - '0') + (strX[j + yLen] - '0');
			if(lpX1 < 0)
				lpX1 += Prime;
		    else
				lpX1 %= Prime;

			lpX2 = lpX2 * 2 - wp2 * (strX[j] - '0') + (strX[j + yLen] - '0');
			if(lpX2 < 0)
				lpX2 += Prime2;
		    else
				lpX2 %= Prime2;
			j++;
		}
	}
	return false;
}

bool LasVegasMatch(const char* strX, const char* strY, int xLen, int yLen)
{
	long lpX = 0, lpY = 0, wp = 1;
	//取素数
	//int Prime = 9973;

	//计算Y串的指纹,计算X(1)的指纹,计算Wp
	for(int i = 0; i < yLen; i++)
	{
		lpY = (lpY * 2 + (strY[i] - '0')) % Prime;
		lpX = (lpX * 2 + (strX[i] - '0')) % Prime;
		wp = (wp * 2) % Prime;
	}

	int j = 0;
	while(j <= xLen - yLen)
	{
		if(lpY == lpX)
		{
			int i = 0;
			for(; i < yLen; i++)
			{
				if(strY[i] != strX[i + j])
				{
				   break;
				}
			}//
			if(i >= yLen)
				return true;
		}
		else if(j == xLen - yLen)
			return false;

		lpX = (lpX * 2) - wp * (strX[j] - '0') + (strX[j + yLen] - '0');
		if(lpX < 0)
			lpX += Prime;
		else
			lpX %= Prime;
		j++;
	}
	return false;
}


int main(int argc, char* argv[])
{
	char strX[MATCH_TIMES][MATCH_LENGTH];
	char strY[MATCH_TIMES][PATTERN_LENGTH];
	int xLength[MATCH_TIMES], yLength[MATCH_TIMES];
	long KMPTime = 0, MCTime = 0, MCTime2 = 0, LSTime = 0;
	int KMPMatchNum = 0, MCMatchNum = 0, MCMatchNum2 = 0, LSMatchNum = 0;
	int AllMatchNum = 0;

	srand( (unsigned)time(NULL));
    primeGen(M);//生成１００个素数；
	int index = rand() % 100;
	int index2 = rand()%100;
    Prime=prime[index];
	Prime2=prime[index2];
	printf("The same prime of Montro cartlo and las vegas algorithms is  %ld\n",Prime);//输出使用的随机素数
	printf("The second prime of Montro carlo is  %ld\n",Prime2);

	SYSTEMTIME BeforeTime, AfterTime;

	for(int j = 0; j < MATCH_T; j++)
	{
		for(int i = 0; i < MATCH_TIMES; i++)
		{
			RandString(&(strX[i][0]), &(strY[i][0]), xLength[i], yLength[i]);
		}

		GetSystemTime(&BeforeTime);
		for(i = 0; i< MATCH_TIMES; i++)
		{
			if(KMPMatch(&(strX[i][0]), &(strY[i][0]), xLength[i], yLength[i]))
				KMPMatchNum++;
		}
		GetSystemTime(&AfterTime);
		KMPTime += ComputeSpan(&BeforeTime, &AfterTime);

		GetSystemTime(&BeforeTime);
		for(i = 0; i< MATCH_TIMES; i++)
		{
			if(MonteCarloMatch1(&(strX[i][0]), &(strY[i][0]), xLength[i], yLength[i]))
				MCMatchNum++;
		}
		GetSystemTime(&AfterTime);
		MCTime += ComputeSpan(&BeforeTime, &AfterTime);
        
		GetSystemTime(&BeforeTime);
		for(i = 0; i< MATCH_TIMES; i++)
		{
			if(MonteCarloMatch2(&(strX[i][0]), &(strY[i][0]), xLength[i], yLength[i]))
				MCMatchNum2++;
		}
		GetSystemTime(&AfterTime);
		MCTime2 += ComputeSpan(&BeforeTime, &AfterTime);

		GetSystemTime(&BeforeTime);
		for(i = 0; i< MATCH_TIMES; i++)
		{
			if(LasVegasMatch(&(strX[i][0]), &(strY[i][0]), xLength[i], yLength[i]))
				LSMatchNum++;
		}
		GetSystemTime(&AfterTime);
		LSTime += ComputeSpan(&BeforeTime, &AfterTime);

	}
	float wrongperofMC1 = ((float)(MCMatchNum-KMPMatchNum)/KMPMatchNum)*100;
	float wrongperofMC2 = ((float)(MCMatchNum2-KMPMatchNum)/KMPMatchNum)*100;
	printf("KMP match times %d, spend time %ld\n", KMPMatchNum, KMPTime);
    printf("with one prime numbers,Mentro Carlo match times %d, spend time %ld,the wrong rate is %.2f%%\n",
		MCMatchNum, MCTime, wrongperofMC1);
	printf("with two prime numbers,Mentro Carlo match times %d, spend time %ld,the wrong rate is %.2f%%\n",
		MCMatchNum2, MCTime2,wrongperofMC2);
	printf("Las Vegas match times %d, spend time %ld\n", LSMatchNum, LSTime);
	return 0;
}

/*输出结果为
The prime is 12377
KMP match times 655,spend time 185(ms)
Mentro carlo match times 862,spend time 123(ms)
Las Vegas match times 655,spend time 296(ms)
总结：
KMP和Las Vegas的出错率为0,而Mentro carlo出错率不为0;
执行时间Las Vegas最长，KMP次之，Mentro carlo最短
*/