kmp.rar_KMP_kmp open_openmp_并行_并行串匹配

#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; } }