fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main(){
  6. 	ios_base::sync_with_stdio(0);
  7. 	cin.tie(0);
  8. 	int n1,n2,m1,m2;
  9. 	cin >> n1 >> n2;
  10. 	char in[n1][n2];
  11. 	for(int i = 0; i < n1; i++){
  12. 		for(int j = 0; j < n2; j++){
  13. 			char c;
  14. 			cin >> c;
  15. 			in[i][j] = c;
  16. 		}
  17. 	}
  18. 	cin >> m1 >> m2;
  19. 	char in1[m1][m2];
  20. 	unsigned long long ppow[m1][m2], seed = 13331,h[m1][m2], h1[m1][m2],hs = 0, ans = 0;
  21. 	ppow[0][0] = 1;
  22. 	for(int i = 0; i < m1; i++){
  23. 		for(int j = 0; j < m2; j++){
  24. 			char c;
  25. 			cin >> c;
  26. 			in1[i][j] = c;
  27. 			if(i && !j){
  28. 				ppow[i][j] = ppow[i-1][m2-1] * seed;
  29. 			}else if(j)ppow[i][j] = ppow[i][j-1] * seed;
  30. 			if(i)
  31. 				h[i][j] = h[i-1][j]+in1[i][j]*ppow[i][j];
  32. 			else h[0][j] = in1[0][j]*ppow[0][j];
  33. 			if(!j)h1[i][j] = h[i][j];
  34. 			else h1[i][j] = h1[i][j-1] + h[i][j];
  35. 		}
  36. 	}
  37. 	for(int i = 0; i < n1; i++){
  38. 		unsigned long long tmp = ppow[i][0];
  39. 		for(int j = 0; j < n2; j++){
  40. 			hs += in[i][j]*tmp;
  41. 			tmp *= seed;
  42. 		}
  43. 	}
  44. 	for(int i = 0; i+n1-1 < m1; i++){
  45. 		for(int j = 0; j+n2-1 < m2; j++){
  46. 			if(!i && !j){
  47. 				if(h1[i+n1-1][j+n2-1] == hs){ans++;cout << "(" << i+1 << "," << j+1 << ")" << endl;}
  48. 			}else if(!i && j){
  49. 				if(h1[i+n1-1][j+n2-1] - h1[i+n1-1][j-1] == ppow[i][j] * hs){ans++;cout << "(" << i+1 << "," << j+1 << ")" << endl;}
  50. 			}
  51. 			else if(i && !j){
  52. 				if(h1[i+n1-1][j+n2-1] - h1[i-1][j+n2-1] == ppow[i][j] * hs){ans++;cout << "(" << i+1 << "," << j+1 << ")" << endl;}
  53. 			}
  54. 			else {
  55. 				if(h1[i+n1-1][j+n2-1] - (h1[i-1][j+n2-1] + h1[i+n1-1][j-1] - h1[i-1][j-1]) == ppow[i][j] * hs){ans++;cout << "(" << i+1 << "," << j+1 << ")" << endl;}
  56. 			}
  57. 		}
  58. 	}
  59. 	if(ans == 0)cout << "NO MATCH FOUND..." << endl;
  60. 	return 0;
  61. }
Runtime error #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cUchRn
language:
C++ (gcc 8.3)
created:
11 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!