jiteshrao

Untitled

May 27th, 2020
29
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define hii cout << "hii" << endl
  5. // #define int ll
  6. #define endl '\n'
  7. #define all(s) s.begin(), s.end()
  8.  
  9. template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
  10. template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
  11. template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
  12. template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
  13.  
  14.  
  15. #ifndef ONLINE_JUDGE
  16. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  17. template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
  18. template <class Arg1, class... Args>
  19. void __f(const char* names, Arg1&& arg1, Args&&... args) {
  20. const char* sep = strchr(names + 1, ',');
  21. cerr.write(names, sep - names) << " : " << arg1 << " ";
  22. __f(sep + 1, args...);
  23. }
  24. #else
  25. #define trace(...) 0
  26. #pragma GCC optimize ("O3")
  27. #pragma GCC optimize ("unroll-loops")
  28. #pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  29. #define _CRT_SECURE_NO_WARNINGS
  30. #endif // ifndef ONLINE_JUDGE
  31.  
  32. const int N = 5e5 + 5;
  33. const int MAXN = 1e4 + 5;
  34. const int M = 3e5;
  35. const int mod = 1e9 + 7;
  36. const int MOD = 1e9 + 7;
  37. // const int INF = 1e15;
  38. const int LG = 21;
  39.  
  40. int arr[N];
  41. int brr[N];
  42. int suff1[N];
  43. int suff2[N];
  44.  
  45. struct Hashs
  46. {
  47. vector<int> hashs;
  48. vector<int> pows;
  49. int P;
  50. int MOD;
  51.  
  52. Hashs() {}
  53.  
  54. Hashs(string &s, int P, int MOD) : P(P), MOD(MOD)
  55. {
  56. int n = s.size();
  57. pows.resize(n+1, 0);
  58. hashs.resize(n+1, 0);
  59. pows[0] = 1;
  60. for(int i=n-1;i>=0;i--)
  61. {
  62. hashs[i]=(1LL * hashs[i+1] * P + s[i] - 'a' + 1) % MOD;
  63. pows[n-i]=(1LL * pows[n-i-1] * P) % MOD;
  64. }
  65. pows[n] = (1LL * pows[n-1] * P)%MOD;
  66. }
  67. int get_hash(int l, int r)
  68. {
  69. int ans=hashs[l] + MOD - (1LL*hashs[r+1]*pows[r-l+1])%MOD;
  70. ans%=MOD;
  71. return ans;
  72. }
  73. };
  74.  
  75. void solve()
  76. {
  77. int n;
  78. while(cin >> n)
  79. {
  80. string input1;
  81. string input2;
  82. cin >> input1 >> input2;
  83. int n = input1.size();
  84. int m = input2.size();
  85. Hashs hh1(input1, 137, 1e9 + 123), hh2(input1, 239, 1e9 + 7);
  86. Hashs gg1(input2, 137, 1e9 + 123), gg2(input2, 239, 1e9 + 7);
  87. int x1 = hh1.get_hash(0, n - 1);
  88. int x2 = hh2.get_hash(0, n - 1);
  89. trace(x1, x2);
  90. for(int i = 0; i + n - 1 <= m - 1; i++)
  91. {
  92. if(gg1.get_hash(i, i + n - 1) == x1 and gg2.get_hash(i, i + n - 1) == x2)
  93. {
  94. cout << i << endl;
  95. }
  96. }
  97. cout << endl;
  98. }
  99. }
  100.  
  101. int32_t main()
  102. {
  103. ios_base:: sync_with_stdio(false);
  104. cin.tie(NULL);
  105. cout.tie(NULL);
  106. // #ifndef ONLINE_JUDGE
  107. // freopen("input.txt", "r", stdin);
  108. // freopen("output.txt", "w", stdout);
  109. // #endif
  110. int t = 1;
  111. // cin >> t;
  112. while(t--)solve();
  113. return 0;
  114. }
RAW Paste Data