fork(4) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #define BASE 163
  4. #define MOD 1000000007
  5. using namespace std;
  6.  
  7. char text[600000], pattern[600000];
  8. long long pow[600000], ht[600000], hp[600000], ans[600000];
  9.  
  10. int main() 
  11. {
  12. 	pow[0] = 1;
  13. 	for (int i = 1; i <= 500000; ++i)
  14. 		pow[i] = (pow[i-1] * BASE) % MOD;	
  15. 	int n;
  16. 	while ((scanf ("%lld", &n)) != EOF)
  17. 	{
  18. 		memset (pattern, '\0', sizeof(pattern));
  19. 		getchar();
  20. 		scanf ("%s", pattern);
  21. 		memset (text, '\0', sizeof(text));
  22. 		getchar();
  23. 		scanf ("%s", text);
  24. 		hp[0] = pattern[0];	
  25. 		for (int i = 1; i < n; ++i)
  26. 		{
  27. 			hp[i] = (hp[i-1] * BASE) % MOD;
  28. 			hp[i] += pattern[i];
  29. 			hp[i] %= MOD;
  30. 		}
  31. 		int m = strlen(text);
  32. 		ht[0] = text[0];
  33. 		for (int i = 1; i < m; ++i)
  34. 		{
  35. 			ht[i] = (ht[i-1] * BASE) % MOD;
  36. 			ht[i] += text[i];
  37. 			ht[i] %= MOD;
  38. 		}
  39. 		int count = 0;
  40. 		memset (ans, 0, sizeof(ans));
  41. 		for (int i = 0; i <= m-n; ++i)
  42. 		{
  43. 			if (i == 0)
  44. 			{
  45. 				if (hp[n-1] == (ht[i+(n-1)]))
  46. 					ans[count++] = i;
  47. 			}
  48. 			else
  49. 			{
  50. 				if (hp[n-1] == (ht[i+(n-1)] - (((ht[i-1] * pow[n])) % MOD)))
  51. 					ans[count++] = i;	
  52. 			}		
  53. 		}
  54. 		for (int i = 0; i < count; ++i)
  55. 			printf ("%lld\n", ans[i]);
  56. 		printf ("\n");	
  57. 	}	
  58. 	return 0;
  59. }
Success #stdin #stdout 0.03s 23224KB
comments (?)
stdin
copy 
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo
stdout
copy 
2
4


3
9
15
21
https://ideone.com/Izpg4B
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!