Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ======================
- [ ___T_ ]
- [ | 6=6 | =>HI :-)]
- [ |__o__| ]
- [ >===]__o[===< ]
- [ [o__] ]
- [ .". ]
- [ |_| ]
- [ ]
- ======================
- */
- #include <bits/stdc++.h>
- using namespace std;
- int main () {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int T = 1;
- //~ cin >> T;
- for (int test_case = 1; test_case <= T; ++test_case) {
- string s;
- cin >> s;
- s += '$';
- int n = (int) s.size();
- pair<char,int> sorted[n];
- int p[n],c[n];
- for (int i = 0; i < n; ++i) sorted[i] = make_pair(s[i],i);
- sort (sorted,sorted + n);
- for (int i = 0; i < n; ++i) p[i] = sorted[i].second;
- c[p[0]] = 0;
- for (int i = 1; i < n; ++i) c[p[i]] = c[p[i - 1]] + (sorted[i].first != sorted[i - 1].first);
- for (int k = 0; (1 << k) < n; ++k) {
- pair<pair<int,int>,int> a[n];
- for (int i = 0; i < n; ++i) a[i] = make_pair(make_pair(c[i],c[(i + (1 << k)) % n]),i);
- sort (a,a + n);
- for (int i = 0; i < n; ++i) p[i] = a[i].second;
- c[p[0]] = 0;
- for (int i = 1; i < n; ++i) c[p[i]] = c[p[i - 1]] + (a[i].first != a[i - 1].first);
- }
- int lcp[n];
- int k = 0;
- lcp[0] = 0;
- for (int i = 0; i < n - 1; ++i) {
- int pi = c[i];
- int j = p[pi - 1];
- while (s[i + k] == s[j + k]) ++k;
- lcp[pi] = k;
- k = max(k - 1,0);
- }
- int64_t sum = 0;
- for (int i = 0; i < n; ++i) {
- sum += (n - p[i]) - (lcp[i] + 1);
- }
- cout << sum << "\n";
- }
- //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement