串匹配.cpp

使用并行计算编程工具OpenMp实现kmp串匹配

#include<iostream>
#include<string>
#include<omp.h>
#include<conio.h>
using namespace std;
#include<time.h>
#include<windows.h>


//next函数和newnext函数的计算算法
void nextfunc(string p,int m,int *next,int *newnext){
    int i,j;
	next[1]=0;
	j=2;
	while(j<=m+1)
	{
		i=next[j-1];
		while(i!=0 && p[i]!=p[j-1])
			i=next[i];
		next[j]=i+1;
		j=j+1;
	}
	newnext[1]=0;
	j=2;
	while(j<=m)
	{
		i=next[j];
		if(i==0 || p[j]!=p[i])
			newnext[j]=i;
		else
			newnext[j]=newnext[i];
		j=j+1;		
	}
}

int main()
{
	int n,m,z;
	int *next,*newnext,*match;
	string p,s,p_temp,s_temp;
	int nthreads;                       //处理器个数
	int timeSystem;			//程序请求运行时间

next=(int *)malloc((m+1)*sizeof(int));
next[0]=0;

newnext=(int *)malloc((m+1)*sizeof(int));
newnext[0]=0;

match=(int *)malloc((n+1)*sizeof(int));
for(int k=0;k<=n;k++)  match[k]=0;

a:	
    cout<<"请输入字符长度n和模式串长度m"<<endl;
	cin>>n>>m;
	cout<<"请输入字符串和模式串"<<endl;
	cin>>s_temp>>p_temp;
	if(s_temp.size()!=n || p_temp.size()!=m)
	{
		cout<<"输入错误，请重新输入！"<<endl;
		goto a;
	}
	p+='0';
    p+=p_temp;
	p[m+1]=0;
	s+='0';
    s+=s_temp;
	s[n+1]=0;

	cout<<"请输入并行处理器数：\n";
	cin>>nthreads;
    nextfunc(p,m,next,newnext);
   

	int threads,tid;
	if(nthreads*m>n)
		threads=int(n/m);
	else
		threads=nthreads;
	omp_set_num_threads(threads);
	int d;
	if(n%threads==0)
		d=n/threads;
	else
		d=n/threads+1;

	 timeSystem=GetTickCount();
#pragma omp parallel 
	{
	   int tid=omp_get_thread_num();
		
       int i=tid*d+1;
	   int j=1;
	   while(i<=(tid+1)*d)
	   { 
	       if(!s[i]) break;
		   while(j!=0 && p[j]!=s[i])
			   j=newnext[j];
		   if(j==m)
		   {
			   match[i-(m-1)]=1;
			   j=next[m+1];
			   i=i+1;
		   }
		   else
		   {
			   i=i+1;
			   j=j+1;
		   }
	   }
	   
       i=(tid+1)*d-m;
	   j=1;
	   while(i<=(tid+1)*d+m-1)
	   {
	       if(!s[i]) break;
		   while(j!=0 && p[j]!=s[i])
			   j=newnext[j];
		   if(j==m)
		   {
			   match[i-(m-1)]=1;
			   j=next[m+1];
			   i=i+1;
		   }
		   else
		   {
			   i=i+1;
			   j=j+1;
		   }
	   }
	}
	for(int l=1;l<=n;l++)
		cout<<match[l];
	cout<<endl;

	cout<<"匹配所占用时间为："<<GetTickCount()-timeSystem<<"毫秒"<<endl;

	cout<<endl<<"请按任意键继续...";
	getch();
	cout<<endl<<endl;
	cout<<"继续：1，退出：2"<<endl;
	cin>>z;
	switch(z){
		case 1:	goto a;break;
		case 2:	cout<<"谢谢使用本系统！";return 1;break;
	}

}