Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- long long P = 257, M = 1e9 + 1;
- long long h1[1000001], h2[1000001], p[1000001], p2[1000001];
- string s1, s2;
- long long sub_hash(int l, int r)
- {
- return (h1[r] - h1[l] * p[r - l] + M * M) % M;
- }
- long long sub_hash2(int l, int r)
- {
- return (h2[r] - h2[l] * p2[r - l] + M * M) % M;
- }
- int main()
- {
- int i, k, n, m, l, r, d;
- cin >> n;
- cin >> s1;
- n--;
- k = 0;
- for (i = n; i >= 0; i--)
- {
- s2[k] = s1[i];
- k++;
- }
- p[0] = 1;
- for (i = 1; i <= n; i++)
- {
- h1[i] = (h1[i - 1] * P + s1[i - 1] - 'a') % M;
- p[i] = (p[i - 1] * P) % M;
- }
- p2[0] = 1;
- for (i = 1; i <= n; i++)
- {
- h2[i] = (h2[i - 1] * P + s2[i - 1] - 'a') % M;
- p2[i] = (p2[i - 1] * P) % M;
- }
- //cout << sub_hash(0, n) << " " << sub_hash2(0, n);
- k = 0;
- for (i = 0; i <= n; i++)
- {
- if (sub_hash(i, n) == sub_hash2(0, n - i))
- {
- k = n - i + 1;
- break;
- }
- }
- for (i = n; i >= 0; i--)
- {
- if (sub_hash(0, i) == sub_hash2(n - i, n) && i >= k)
- {
- k = i + 1;
- break;
- }
- }
- cout << k;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement