首页 > 代码库 > UVA 11019
UVA 11019
Problem H
Matrix Matcher
Input: Standard Input
Output: Standard Output
Given an N * M matrix, your task is to find the number of occurences of an X * Y pattern.
Input
The first line contains a single integer t(t ≤ 15), the number of test cases.
For each case, the first line contains two integers N and M (N, M ≤ 1000). The next N lines contain M characters each.
The next line contains two integers X and Y (X, Y ≤ 100). The next X lines contain Y characters each.
Output
For each case, output a single integer in its own line, the number of occurrences.
Sample Input Output for Sample Input
2 1 1 x 1 1 y 3 3 abc bcd cde 2 2 bc cd | 0 2
|
一个二维的hash,可以先对每一行hash,然后在对列hash
1 #include<iostream> 2 #include<cstdio> 3 #include<string.h> 4 #include<vector> 5 #include<algorithm> 6 #include<map> 7 using namespace std; 8 typedef unsigned long long ull; 9 #define mmax 100000+1010 ull base,seed=131,ansx[1100][1100],ansy[1100][1100],aans[1001000];11 int n,m;12 char p[1100][1100],q[110][110];13 int lfind(ull tail){14 int l=0,r=n*m-1,mid,ans=-1;15 while(l<=r){16 mid=(l+r)>>1;17 if(aans[mid]>=tail) {18 if(aans[mid]==tail) ans=mid;19 r=mid-1;20 }21 else l=mid+1;22 }23 return ans;24 }25 int rfind(ull tail){26 int l=0,r=n*m-1,mid,ans=-1;27 while(l<=r){28 mid=(l+r)>>1;29 if(aans[mid]<=tail) {30 if(aans[mid]==tail) ans=mid;31 l=mid+1;32 }33 else r=mid-1;34 }35 return ans;36 }37 int main(){38 int t;cin>>t;39 while(t--){40 cin>>n>>m;getchar();41 for(int i=0;i<n;i++)42 scanf("%s",p[i]);43 // cout<<"------"<<endl;44 int x,y;45 cin>>x>>y;46 for(int i=0;i<x;i++)47 scanf("%s",q[i]);48 // cout<<"------"<<endl;49 if(x>n||y>m){50 cout<<0<<endl;51 continue;52 }53 memset(ansx,0,sizeof(ansx));54 base=1;55 for(int i=1;i<y;i++) base*=seed;56 for(int i=0;i<n;i++){57 for(int j=0;j<y;j++) ansx[i][0]=ansx[i][0]*seed+p[i][j];58 for(int j=y;j<m;j++) ansx[i][j-y+1]=(ansx[i][j-y]-p[i][j-y]*base)*seed+p[i][j];59 }60 memset(ansy,0,sizeof(ansy));61 base=1;62 for(int i=1;i<x;i++) base*=seed;63 for(int i=0;i<m;i++){64 for(int j=0;j<x;j++) ansy[0][i]=ansy[0][i]*seed+ansx[j][i];65 for(int j=x;j<n;j++) ansy[j-x+1][i]=(ansy[j-x][i]-ansx[j-x][i]*base)*seed+ansx[j][i];66 }67 int id=0;68 for(int i=0;i<n;i++)69 for(int j=0;j<m;j++)70 aans[id++]=ansy[i][j];71 sort(aans,aans+id);72 ull tail=0;73 for(int i=0;i<x;i++){74 ull tmp=0;75 for(int j=0;j<y;j++) tmp=tmp*seed+q[i][j];76 tail=tail*seed+tmp;77 }78 if(lfind(tail)==-1){79 cout<<0<<endl;80 continue;81 }82 printf("%d\n",rfind(tail)-lfind(tail)+1);83 }84 }
UVA 11019
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。