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> a_[n];
- int p[n],c[n];
- for (int i = 0; i < n; ++i) a_[i] = make_pair(s[i],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);
- 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);
- }
- for (int i = 0; i < n; ++i) cout << p[i] << " " << s.substr(p[i],n - p[i]) << "\n";
- }
- //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement