Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define len(s) (s).size()
- using namespace std;
- const int ALPHABET = 256, n = 1e6;
- int c[n], new_c[n], suf[n], new_suf[n], starts[n];
- void suffix_array(string s) {
- s.push_back(0);
- int n = len(s);
- for (int i = 0; i < n; i++) {
- suf[i] = i;
- c[i] = s[i];
- starts[s[i] + 1]++;
- }
- int sum = 0;
- for (int i = 0; i < n; i++) {
- sum += starts[i], starts[i] = sum;
- }
- for (int l = 0; l < n; l = (l ? 2 * l : 1)) {
- for (int i = 0; i < n; i++) {
- int pos = (suf[i] - l + n);
- if (pos >= n) pos -= n;
- new_suf[starts[c[pos]]++] = pos;
- }
- int type = -1;
- long long last = -1;
- for (int i = 0; i < n; i++) {
- int v = new_suf[i];
- if (last != (c[v] * 1ll * max(n, ALPHABET + 1) + c[(v + l) % n])) {
- last = (c[v] * 1ll * max(n, ALPHABET + 1) + c[(v + l) % n]);
- starts[++type] = i;
- }
- new_c[v] = type;
- }
- memcpy(new_c, c, sizeof c);
- memcpy(new_suf, suf, sizeof suf);
- }
- }
- signed main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- string s;
- cin >> s;
- s += s;
- s += s;
- suffix_array(s);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement