Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int long long
- using namespace std;
- const int MOD = 1999999943;
- const int MD = 1000000007;
- int BASE = 239;
- struct hash_str {
- vector <int> h, p;
- vector <int> h1, p1;
- hash_str(string s) {
- int n = (int) s.size();
- h.resize(n);
- p.resize(n);
- h1.resize(n);
- p1.resize(n);
- h[0] = h1[0] = s[0];
- p[0] = p1[0] = 1;
- for (int i = 1; i < n; i++) {
- h[i] = (h[i - 1] * BASE + s[i]) % MOD;
- h1[i] = (h1[i - 1] * BASE + s[i]) % MD;
- p[i] = (p[i - 1] * BASE) % MOD;
- p1[i] = (p1[i - 1] * BASE) % MD;
- }
- }
- int get(int l, int r) {
- int res = h[r] - (l ? (h[l - 1] * p[r - l + 1]) % MOD : 0);
- if (res < 0) {
- res += MOD;
- }
- return res;
- }
- int gt(int l, int r) {
- int res = h1[r] - (l ? (h1[l - 1] * p1[r - l + 1]) % MD : 0);
- if (res < 0) {
- res += MD;
- }
- return res;
- }
- };
- set <pair <int, int> > diff1, diff2;
- main() {
- srand(time(NULL));
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- BASE = 0;
- while (BASE < 255) {
- BASE = rand();
- }
- string s, t;
- cin >> s;
- t = s;
- reverse(t.begin(), t.end());
- hash_str h(s);
- hash_str q(t);
- int n = s.size();
- vector <int> p(n);
- for (int i = 0; i < n; i++) {
- int l = 1, r = n;
- while (l < r - 1) {
- int m = (l + r) / 2;
- if (i + m - 1 < n && i - m + 1 >= 0) {
- int left = i - m + 1;
- int right = i + m - 1;
- if (h.get(left, right) == q.get(n - 1 - right, n - 1 - left)) {
- l = m;
- } else {
- r = m;
- }
- } else {
- r = m;
- }
- }
- int d = l;
- int left = i - d + 1, right = i + d - 1;
- while (d > 0) {
- int left = i - d + 1, right = i + d - 1;
- if (h.get(left, right) != q.get(n - 1 - right, n - 1 - left)) {
- break;
- }
- if (left > right) {
- break;
- }
- int hush = h.get(left, right);
- int hesh = h.gt(left, right);
- if (diff1.count(make_pair(hush, hesh))) {
- break;
- } else {
- diff1.insert(make_pair(hush, hesh));
- p[right]++;
- d--;
- }
- }
- }
- for (int i = 0; i < n; i++) {
- int l = 0, r = n;
- while (l < r - 1) {
- int m = (l + r) / 2;
- if (i + m < n && i - m + 1 >= 0) {
- int left = i - m + 1;
- int right = i + m;
- if (h.get(left, right) == q.get(n - 1 - right, n - 1 - left)) {
- l = m;
- } else {
- r = m;
- }
- } else {
- r = m;
- }
- }
- int d = l;
- int left = i - d + 1, right = i + d;
- while (d > 0) {
- int left = i - d + 1, right = i + d;
- if (h.get(left, right) != q.get(n - 1 - right, n - 1 - left)) {
- break;
- }
- if (left > right) {
- break;
- }
- int hush = h.get(left, right);
- int hesh = h.gt(left, right);
- if (diff2.count(make_pair(hush, hesh))) {
- break;
- } else {
- diff2.insert(make_pair(hush, hesh));
- p[right]++;
- d--;
- }
- }
- }
- int ans = 0;
- for (int i = 0; i < n; i++) {
- ans += p[i];
- cout << ans << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment