# Untitled

Mar 16th, 2023
359
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. using namespace std;
3. using ll = long long;
4. #define rep(i, a, b) for(int i = a; i < (b); ++i)
5. #define all(x) begin(x), end(x)
6. #define sz(x) (int)(x).size()
7. typedef long long ll;
8. typedef pair<int, int> pii;
9. typedef vector<int> vi;
10. struct SuffixArray {
11.     vi sa, lcp;
12.     SuffixArray(string& s, int lim=256) { // or basic_string<int>
13.         int n = sz(s) + 1, k = 0, a, b;
14.         vi x(all(s)+1), y(n), ws(max(n, lim)), rank(n);
15.         sa = lcp = y, iota(all(sa), 0);
16.         for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
17.             p = j, iota(all(y), n - j);
18.             rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
19.             fill(all(ws), 0);
20.             rep(i,0,n) ws[x[i]]++;
21.             rep(i,1,lim) ws[i] += ws[i - 1];
22.             for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
23.             swap(x, y), p = 1, x[sa[0]] = 0;
24.             rep(i,1,n) a = sa[i - 1], b = sa[i], x[b] =
25.                 (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
26.         }
27.         rep(i,1,n) rank[sa[i]] = i;
28.         for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
29.             for (k && k--, j = sa[rank[i] - 1];
30.                     s[i + k] == s[j + k]; k++);
31.     }
32. };
33. int main() {
34.     string s; cin >> s;
35.     SuffixArray arr(s);
36.     ll n = s.size(), sum = n * (n + 1) / 2;
37.     sum -= accumulate(arr.lcp.begin(), arr.lcp.end(), 0LL);
38.     cout << sum << endl;
39.     return 0;
40. }
41.