string s; vector p(n); iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&](int i, int j){ // s.data() + i // s.data() + j // bs k : hash [i,i+k) and [j,j+k) }); // [i, i+len) uint32_t getHash(int i, int len) { return (h[i+len] - (uint64_t)h[i]*deg[len]) % mod; } // p, mod int mod1 = 1e9 + 7 // простое int mod2 = 1e9 + 9 // простое p = random // [0,mod) // 1e18 : double(8) sign*x*2^k // double 15-16 __int128 mod = (int64_t)1e18 + 3; // mod = 2^{64} // Суфф массив за nlogn abc# abc# bc#a c#ab #abc // Сортируем циклические сдвиги // abcde // abc k=3 // bcd // cde // dea // eab // Алгоритм // База: k=1 // Отсортируем символы строки // nlogn // n+|Sigma| // База: color[i] = s[i] // [0..n) // Переход: k -> 2k : O(n) 0. p = {0, 1, 2, ..., n-1} 1. sort(p) : f(i) {color[i], color[i+k]} 2. cc = 0 for (int j = 0; j < n; j++) i1 = i, i = p[j] if f(i) != f(i1) // [i,i+2k) != [i1,i1+2k) cc++ color2[i] = cc color = color2 // => O(nlogn) // O(n log^2 n) vector SA(string s) { int n = s.size(); vector c(n), p(n), c2(n); forn(i, n) c[i] = s[i]; iota(p.begin(), p.end(), 0); for (int k = 1; k < n; k *= 2) { #define f(i) make_pair(c[i],c[i+k]) sort(p.begin(), p.end(), [&](i, j) { return f(i) < f(j); }); int cc = 0, i = -1, i1; forn(j, n) { i1 = i, i = p[j]; cc += (i1 != -1 && f(i) != f(i1)); c[i] = cc } c = c2; } return p; } // O(n log n) vector SA(string s) { int n = s.size(); vector c(n), p(n), c2(n), p2(n); forn(i, n) c[i] = s[i]; iota(p.begin(), p.end(), 0); sort(p.begin(), p.end(), [&](i, j) { return s[i] < s[j]; }); for (int k = 1; k < n; k *= 2) { // p2 ??? O(n) vector cnt(n), pos(n+1); for (int x : c) cnt[x]++; forn(i, n) pos[i+1] = pos[i] + cnt[i]; forn(j, n) { int i = p[j]; // 2-я половина int i1 = (i - k + n) % n; // 1-я p2[pos[c[i1]]++] = i1; } #define f(i) make_pair(c[i],c[i+k]) int cc = 0, i = -1, i1; forn(j, n) { i1 = i, i = p2[j]; cc += (i1 != -1 && f(i) != f(i1)); c[i] = cc } c = c2, p = p2; } return p; } // алгоритм Касаи // p1 = p^{-1} i = p1[x+0] j = p1[x+1] Thm: lcp[j] >= lcp[i] - 1 lcp[i] = LCP(s + p[i], s + p[i+1]) lcp[j] = LCP(s + p[j], s + p[j+1]) vector LCP(vector p) { // p=SA int n = p.size(); vector lcp(n), p1(n); forn(i, n) // обратная перестановка p1[p[i]] = i; int k = 0; forn(i, n) { // s[i,n) // if (k == n) k = 0; // костыль k = max(k - 1, 0); // k = 0 int x = p1[i]; while (s[i + k] == s[p[x+1] + k]) k++; lcp[x] = k; } return lcp; }