Advertisement
Guest User

Untitled

a guest
Aug 30th, 2016
336
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.28 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<algorithm>
  5. #include<vector>
  6. #include<math.h>
  7. #include<string>
  8. #include<sstream>
  9. #include<set>
  10. #include<map>
  11. #include<stack>
  12. #include<queue>
  13. #include<deque>
  14. #include<memory.h>
  15. #include<ctime>
  16. #include<cassert>
  17. #include<limits.h>
  18. #include<unordered_map>
  19. #include<unordered_set>
  20.  
  21. #define pb push_back
  22. #define sz(a) (int)a.size()
  23. #define bs binary_search
  24. #define np next_permutation
  25. #define mp make_pair
  26. #define all(a) a.begin(),a.end()
  27. #define read(a) scanf("%d", &a)
  28. #define writeln(a) printf("%d\n", a);
  29. #define forn(i, n) for (int i = 0; i < n; ++i)
  30. #define forv(i, v) for (int i = 0; i < sz(v); ++i)
  31. #define forsint(it, s) for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
  32. #define _(a, b) memset(a, b, sizeof a)
  33. #define pii pair<int, int>
  34. #define pll pair<long long, long long>
  35.  
  36. typedef long long ll;
  37. typedef unsigned long long ull;
  38.  
  39. using namespace std;
  40.  
  41. template<class T> inline T sqr(T x) { return x * x; }
  42.  
  43. const double pi = acos(-1.0), eps = 1e-9, e = exp(1.0);
  44. const int INF = 1000 * 1000 * 1000 + 7, MAXN = 100005, MOD = 1000000007, MAXBIT = 30;
  45. const ll INFL = 1e+18;
  46.  
  47. void prepare(string s) {
  48. #ifdef _DEBUG
  49. freopen("input.txt", "r", stdin);
  50. freopen("output.txt","w",stdout);
  51. #else
  52. if (sz(s) != 0) {
  53. freopen((s + ".in").c_str(), "r", stdin);
  54. freopen((s + ".out").c_str(), "w", stdout);
  55. }
  56. #endif
  57. }
  58.  
  59. int n;
  60. string s, t;
  61. ll pp1[3*MAXN], pp2[3*MAXN], hs1[3*MAXN], hs2[3*MAXN], ht1[3*MAXN], ht2[3*MAXN];
  62.  
  63. long long getHash1(int l, int r) {
  64. long long h = ht1[r];
  65. if (l > 0)
  66. h -= ht1[l - 1];
  67. h *= pp1[n - 1 - r];
  68. return h;
  69. }
  70.  
  71. long long getHash1s(int l, int r) {
  72. long long h = hs1[r];
  73. if (l > 0)
  74. h -= hs1[l - 1];
  75. h *= pp1[n - 1 - r];
  76. return h;
  77. }
  78.  
  79. long long getHash2(int l, int r) {
  80. long long h = ht2[r];
  81. if (l > 0)
  82. h = (h - ht2[l - 1] + INF) % INF;
  83. h = (h * pp2[n - 1 - r]) % INF;
  84. return h;
  85. }
  86.  
  87. long long getHash2s(int l, int r) {
  88. long long h = hs2[r];
  89. if (l > 0)
  90. h = (h - hs2[l - 1] + INF) % INF;
  91. h = (h * pp2[n - 1 - r]) % INF;
  92. return h;
  93. }
  94.  
  95. void solve()
  96. {
  97. cin >> n >> s >> t;
  98.  
  99. if (sz(s) != sz(t)) {
  100. cout << -1;
  101. exit(0);
  102. }
  103.  
  104. pp1[0] = pp2[0] = 1;
  105. for (int i = 1; i <= n; i++) {
  106. pp1[i] = pp1[i-1] * 53;
  107. pp2[i] = (pp2[i-1] * 53) % INF;
  108. }
  109.  
  110. hs1[0] = s[0] - 'a' + 1;
  111. hs2[0] = (s[0] - 'a' + 1) % INF;
  112. ht1[0] = t[0] - 'a' + 1;
  113. ht2[0] = (t[0] - 'a' + 1) % INF;
  114.  
  115. for (int i = 1; i < n; i++) {
  116. hs1[i] = hs1[i - 1] + pp1[i] * (s[i] - 'a' + 1);
  117. hs2[i] = (hs2[i - 1] + pp2[i] * (s[i] - 'a' + 1)) % INF;
  118.  
  119. ht1[i] = ht1[i - 1] + pp1[i] * (t[i] - 'a' + 1);
  120. ht2[i] = (ht2[i - 1] + pp2[i] * (t[i] - 'a' + 1)) % INF;
  121. }
  122.  
  123. for (int i = sz(t)-1; i >= 0; i--) {
  124. ll hashRight = getHash1(i, sz(t)-1);
  125. ll hashRight2 = getHash2(i, sz(t)-1);
  126.  
  127. ll hashLeft = getHash1s(sz(t) - i, sz(t)-1);
  128. ll hashLeft2 = getHash2s(sz(t) - i, sz(t) - 1);
  129.  
  130. if (hashRight == getHash1s(0, n - i - 1) && hashLeft == getHash1(0, i - 1)) {
  131. if (hashRight2 == getHash2s(0, n - i - 1) && hashLeft2 == getHash2(0, i - 1)) {
  132. cout << i;
  133. exit(0);
  134. }
  135. }
  136. }
  137.  
  138. cout << -1;
  139.  
  140. }
  141.  
  142. int main()
  143. {
  144. prepare("");
  145.  
  146. solve();
  147.  
  148. return 0;
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement