fork(3) download
  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
stdin
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo
stdout
2
4


3
9
15
21