fork(2) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. #include <string>
  7. using namespace std;
  8. char a[1000000], b[1000000];
  9. long long pot_szybkie(long long a, long long n, long long q) {
  10. 	long long w = 1;
  11. 	while (n > 0) {
  12. 		if (n % 2 == 1)w = (w*a) % q;
  13. 		a *= a;
  14. 		n /= 2;
  15. 	}
  16. 	return w%q;
  17. }
  18. int main() {
  19. 	int n;
  20. 	scanf("%d", &n);
  21. 	for (int i = 0; i < n; ++i) {
  22. 		int s;
  23. 		scanf("%d", &s);
  24. 		scanf("%s", a);
  25. 		scanf("%s", b);
  26. 		int dl_a = s;
  27. 		int dl_b = strlen(b);
  28. 		long long p = 61;
  29. 		long long q = 1000000007, h = pot_szybkie(p, dl_a - 1, q) % q;
  30. 		long long hasz1 = 0, hasz2 = 0;
  31. 		for (int i = 0; i < dl_a; ++i) {
  32. 			hasz1 = ((hasz1*p) % q + a[i]) % q;
  33. 		}
  34. 		hasz1 %= q;
  35. 		for (int i = 0; i < dl_a; ++i) {
  36. 			hasz2 = ((hasz2*p) % q + b[i]) % q;
  37. 		}
  38. 		hasz2 %= q;
  39. 		for (int i = 0; i <= dl_b - dl_a; ++i) {
  40. 			if (hasz1 == hasz2) {
  41. 				int j = 0;
  42. 				bool fla = 0;
  43. 				while (j < dl_a) {
  44. 					if (a[j] != b[i + j]) {
  45. 						fla = 1;
  46. 						break;
  47. 					}
  48. 					++j;
  49. 				}
  50. 				if (fla == 0)
  51. 					printf("%d\n", i);
  52. 			}
  53. 			hasz2 = (p*(hasz2 - (b[i])*h) % q + b[i + dl_a]) % q;
  54. 			if (hasz2 < 0)hasz2 += q;
  55. 		}
  56. 	}
  57. 	return 0;
  58. }
Success #stdin #stdout 0s 17192KB
comments (?)
stdin
copy 
3
2
na
banananobano
6
foobar
foo
9
foobarfoo
barFOObarfoobarfoobarfoobarfoo
stdout
copy 
2
4
9
15
21
https://ideone.com/MFhNpG
language:
C++14 (gcc 8.3)
created:
6 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!