Advertisement
NHumme

KEK

Oct 29th, 2018
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long P = 257, M = 1e9 + 1;
  6. long long h1[1000001], h2[1000001], p[1000001], p2[1000001];
  7. string s1, s2;
  8.  
  9. long long sub_hash(int l, int r)
  10. {
  11.     return (h1[r] - h1[l] * p[r - l] + M * M) % M;
  12. }
  13.  
  14. long long sub_hash2(int l, int r)
  15. {
  16.     return (h2[r] - h2[l] * p2[r - l] + M * M) % M;
  17. }
  18.  
  19. int main()
  20. {
  21.     int i, k, n, m, l, r, d;
  22.     cin >> n;
  23.     cin >> s1;
  24.     n--;
  25.     k = 0;
  26.     for (i = n; i >= 0; i--)
  27.     {
  28.         s2[k] = s1[i];
  29.         k++;
  30.     }
  31.     p[0] = 1;
  32.     for (i = 1; i <= n; i++)
  33.     {
  34.         h1[i] = (h1[i - 1] * P + s1[i - 1] - 'a') % M;
  35.         p[i] = (p[i - 1] * P) % M;
  36.     }
  37.     p2[0] = 1;
  38.     for (i = 1; i <= n; i++)
  39.     {
  40.         h2[i] = (h2[i - 1] * P + s2[i - 1] - 'a') % M;
  41.         p2[i] = (p2[i - 1] * P) % M;
  42.     }
  43.     //cout << sub_hash(0, n) << " " << sub_hash2(0, n);
  44.     k = 0;
  45.     for (i = 0; i <= n; i++)
  46.     {
  47.         if (sub_hash(i, n) == sub_hash2(0, n - i))
  48.         {
  49.             k = n - i + 1;
  50.             break;
  51.         }
  52.     }
  53.     for (i = n; i >= 0; i--)
  54.     {
  55.         if (sub_hash(0, i) == sub_hash2(n - i, n) && i >= k)
  56.         {
  57.             k = i + 1;
  58.             break;
  59.         }
  60.     }
  61.     cout << k;
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement