fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define fi first
  4. #define se second
  5. #define mp make_pair
  6. #define pb push_back
  7. #define pf push_front
  8. #define popb pop_back
  9. #define popf pop_front
  10.  
  11. using namespace std;
  12.  
  13. const int Nmax = 1001;
  14. const int sl = 2;
  15. const int64_t Mod[sl] = {1000000009LL, 1000002277LL};
  16. const int64_t base = 123456LL;
  17.  
  18. int n,m,a[Nmax][Nmax],b[Nmax][Nmax],x,y,op[Nmax];
  19. int64_t c[sl][Nmax],d[sl][Nmax][Nmax],e[sl][Nmax];
  20.  
  21. void input(){
  22.     ///Đọc mảng A
  23.     scanf("%d%d",&n,&m);
  24.     for (int i=1;i<=n;++i)
  25.         for (int j=1;j<=m;++j)
  26.             scanf("%d",&a[i][j]);
  27.     ///Đọc mảng B
  28.     scanf("%d%d",&x,&y);
  29.     for (int i=1;i<=x;++i)
  30.         for (int j=1;j<=y;++j)
  31.             scanf("%d",&b[i][j]);
  32. }
  33.  
  34. bool check_1(int u, int v){
  35.     /// Kiểm tra 2 vị u, v trong mảng C có giống nhau hay ko
  36.     for (int z=0;z<sl;++z)
  37.         if (c[z][u]!=c[z][v])
  38.             return false;
  39.     return true;
  40. }
  41.  
  42. void xuly(){
  43.     /// biến đổi mảng B thành mảng C
  44.     for (int i=1;i<=y;++i)
  45.         for (int z=0;z<sl;++z)
  46.             for (int j=1;j<=x;++j)
  47.                 c[z][i]=(c[z][i]*base+b[j][i])%Mod[z];
  48.     /// Xây dựng mảng op cho C
  49.     for (int i=2,j=0;i<=y;++i){
  50.         while(j&&check_1(i,j+1)==false) j=op[j];
  51.         if (check_1(i,j+1)) ++j;
  52.         op[i]=j;
  53.     }
  54.     /// biến đổi mảng A thành mảng D
  55.     for (int i=1;i<=n;++i)
  56.         for (int j=1;j<=m;++j)
  57.             for (int z=0;z<sl;++z)
  58.                 d[z][i][j]=(d[z][i-1][j]*base+a[i][j])%Mod[z];
  59. }
  60.  
  61. int64_t pw[sl];
  62.  
  63. bool check_2(int u, int v){
  64.     /// Kiểm tra vị trí u trong mang e có = vi trí v trong mảng c ko
  65.     for (int z=0;z<sl;++z)
  66.         if (e[z][u]!=c[z][v])
  67.             return false;
  68.     return true;
  69. }
  70.  
  71. int main(){
  72.     #ifndef ONLINE_JUDGE
  73.         freopen("k.inp","r",stdin);
  74.         freopen("k.out","w",stdout);
  75.     #endif // ONLINE_JUDGE
  76.     input();
  77.     xuly();
  78.     for (int z=0;z<sl;++z){
  79.         pw[z]=1;
  80.         for (int j=1;j<=x;++j)
  81.             pw[z]=(pw[z]*base)%Mod[z];
  82.     }
  83.     /// Tìm kiếm
  84.     for (int i=1;i+x-1<=n;++i){
  85.         /// Tạo mảng e
  86.         for (int j=1;j<=m;++j){
  87.             for (int z=0;z<sl;++z){
  88.                 e[z][j]=d[z][i+x-1][j]-(d[z][i-1][j]*pw[z]%Mod[z]);
  89.                 e[z][j]%=Mod[z];
  90.                 if (e[z][j]<0) e[z][j]+=Mod[z];
  91.             }
  92.         }
  93.         for (int j=1,jj=0;j<=m;++j){
  94.             while(jj&&check_2(j,jj+1)==false) jj=op[jj];
  95.             if (check_2(j,jj+1)) ++jj;
  96.             if (jj==y){
  97.                 printf("%d %d",i,j-y+1);
  98.                 return 0;
  99.             }
  100.         }
  101.     }
  102.     printf("%d",-1);
  103. }
  104.  
Success #stdin #stdout 0s 4184KB
comments (?)
stdin
copy 
10 9
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
1 2 1 2 3 4 5 4 5
0 4 6 8 1 3 5 7 6
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
1 2 1 2 3 5 6 7 5
6 7 8 9 1 3 5 7 6
6 7 8 9 6 7 8 9 2
6 7 8 9 6 7 8 9 2
2 3
3 2 1
5 4 5
stdout
copy 
2 7
https://ideone.com/cueFDp
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!