1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
| #include<bits/stdc++.h> #define int long long using namespace std; int n,m,a,b,q; const int moda=1e7+7,basea1=2,basea2=9191891; const int modb=1e7+9,baseb1=7,baseb2=6498497; int qba1[1005],qba2[1005]; int qbb1[1005],qbb2[1005]; int sa[1005][1005]; int ht[1005][1005]; bool hasha[10000010]; bool hashb[10000010]; char s[1005][1005]; void hashta() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ht[i][j]=((ht[i][j-1]*basea1)%moda+sa[i][j])%moda; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ht[i][j]=((ht[i-1][j]*basea2)%moda+ht[i][j])%moda; for(int i=a;i<=n;i++) for(int j=b;j<=m;j++) { int tmp=((ht[i][j]-(ht[i][j-b]*qba1[b])%moda-(ht[i-a][j]*qba2[a])%moda+((ht[i-a][j-b]*qba1[b])%moda*qba2[a])%moda)%moda+moda)%moda; hasha[tmp]=1; } } void hashtb() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ht[i][j]=((ht[i][j-1]*baseb1)%modb+sa[i][j])%modb; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ht[i][j]=((ht[i-1][j]*baseb2)%modb+ht[i][j])%modb; for(int i=a;i<=n;i++) for(int j=b;j<=m;j++) { int tmp=((ht[i][j]-(ht[i][j-b]*qbb1[b])%modb-(ht[i-a][j]*qbb2[a])%modb+((ht[i-a][j-b]*qbb1[b])%modb*qbb2[a])%modb)%modb+modb)%modb; hashb[tmp]=1; } } int hashon() { for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) ht[i][j]=((ht[i][j-1]*basea1)%moda+sa[i][j])%moda; for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) ht[i][j]=((ht[i-1][j]*basea2)%moda+ht[i][j])%moda; bool ta=hasha[ht[a][b]]; for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) ht[i][j]=((ht[i][j-1]*baseb1)%modb+sa[i][j])%modb; for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) ht[i][j]=((ht[i-1][j]*baseb2)%modb+ht[i][j])%modb; bool tb=hashb[ht[a][b]]; return ta&&tb; } void pre() { qba1[0]=1; qba2[0]=1; for(int i=1;i<1005;i++) qba1[i]=(qba1[i-1]*basea1)%moda; for(int i=1;i<1005;i++) qba2[i]=(qba2[i-1]*basea2)%moda; qbb1[0]=1; qbb2[0]=1; for(int i=1;i<1005;i++) qbb1[i]=(qbb1[i-1]*baseb1)%modb; for(int i=1;i<1005;i++) qbb2[i]=(qbb2[i-1]*baseb2)%modb; } signed main() { pre(); scanf("%d%d%d%d",&n,&m,&a,&b); for(int i=1;i<=n;i++) scanf("%s",s[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sa[i][j]=s[i][j]-'0'; hashta(); hashtb(); scanf("%d",&q); for(int t=1;t<=q;t++) { for(int i=1;i<=a;i++) scanf("%s",s[i]+1); for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) sa[i][j]=s[i][j]-'0'; printf("%d\n",hashon()); } }
|