montecarlo.h

MonteCarlo实现

#include"primer.h"

//////////////////////////////////////////////////
//求字符串的指纹
string lp(string str,int p)
{
  int length=str.size();
  int sum=0;
  for(int i=0;i<length;i++)
  {
	  if(str[i]=='1')
		  sum+=pow(2.0,length-i-1);
  }

  sum=sum%p;
  return convert(sum);
  
}

//求下一个相邻字符串,根据lp(x[j])求lp(x[j+1])
string lpNext(string lpxj,string x,int j,int n,int p)
{ //将二进制转化为十进制,m为模式串y的长度;p随机生成的素数
  int length=lpxj.size();
  int sum=0;
  int tmp=0;
  for(int i=0;i<length;i++)
	  if(lpxj[i]=='1')
		  sum+=pow(2.0,length-i-1);

  sum=sum%p;
  
  string strm=convert(n); 
  int lstrm=strm.size();
  int xj=-1;
  int xjpm=-1;
  
  if(x[j]=='1')
	  xj=1;
  else
	  xj=0;
  
  if(x[j+n]=='1')
	  xjpm=1;
  else
	  xjpm=0;
  
  tmp=(2*sum-expmod(2,n,p,lstrm,strm)*xj+xjpm)%p;
  
  return convert(tmp);
}


//////////////////////////////////////////////
//x，y二进制形式的字符串，m，n分别为x，y的长度
//判断y是否为x的子串，如果是返回1，否则返回0
int MonteCarlo(int m,int n,string x,string y)
{  
  int i=0;//控制while循环
  int p;
  int j=0;
  int M=2*m*m;
  if(x.size()!=0&&y.size()!=0)
  {
   p=primeGenerate(M);
   string lpx,lpy;
  
  while(i<n) 
  {
	  lpx=lpx+x[i];
	  i++;
  }

  lpx=lp(lpx,p);
  lpy=lp(y,p);
  
  while(j<=m-n)
  {
    if(lpx==lpy) return 1;
	else
	{
	 lpx=lpNext(lpx,x,j,n,p);
	 j++;
	}
  }
  }
  
 return 0;
}