1 简单介绍
2 随机算法
3 指纹计算
4 计算步骤
假匹配
当Ip(Y)和Ip(X(j))不相等，那么Y和X(j)一定不匹配；但是逆命题是错误的，即两指纹相同，X与X(j)也不一定匹配，即为假匹配。这就是蒙特卡罗算法的体现之处，即一定有解，但不应正确。5 代码
默认全是小写字母由于素数计算范围大，假设文本串长度短，n=5;本代码还可以继续改正，如文本长度、模式长度、字符类型等#include <iostream>#include<stdlib.h>#include <cmath>using namespace std;string X,Y; //默认全是小写字符 const int n=5;//文本串长度 const int m=2; //模式长度 const int M=2*m*n*n;//M以内的素数集int prim[M]={0};//素数集合 int Plen = 0; //素数集合长度 //产生素数集合 int isPrim(){prim[1]=2;int Plen=1;for(int i=3;i<=M;i+=2){//枚举每个数bool flag = true;for(int j=2;j<=sqrt(i);j++){if(i%j==0){flag=false;break;}}if(flag) prim[++Plen]=i;}return Plen;}//指纹计算int fingerPrintCompute(string s,int j,int wp,int p){int fg = 0;for(int i=0;i<=m-1;i++){fg += (wp/2)*(s[j+i]-'a')%p; wp = wp/2;}return fg;}//PatternMatching int PatternMatching(){int p = prim[rand()%Plen];int j = 0; //伪代码是j=1，但字符串1-th下表是0，所以j=0，原理一样。 int WP = ((int)pow(2*1.0,m*1.0))%p;int Ip_Y = fingerPrintCompute(Y,0,WP,p);int Ip_Xj = fingerPrintCompute(X,j,WP,p);while(j<=n-m+1){if(Ip_Xj==Ip_Y)return j;Ip_Xj = (2*Ip_Xj-WP*(X[j]-'a')+(X[j+m]-'a'))%p;j++;}return 0;}int main(int argc, char *argv[]){cout<<"输入长度"<<n<<"的字符串和长度"<<m<<"的模式"<<endl; cin>>X>>Y; //输入文本串、模式Plen=isPrim();cout<<"从小于"<<M<<"的素数集长度是 "<<Plen<<endl; int position = PatternMatching();cout<<"模式第一次出现在文本串的位置下表是"<<position<<endl; return 0;}
6 测试
输入：asvas
as
输出：从小于100的素数集长度是 25
模式第一次出现在文本串的位置下表是0
如果觉得《随机算法——蒙特卡罗算法——模式匹配问题》对你有帮助，请点赞、收藏，并留下你的观点哦！
