首页 > 代码库 > UVA 11019

UVA 11019

2024-11-05 14:57:02   208人阅读

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


联系
我们