Suffix Array + LCP
O(n log² n)Sort all suffixes by doubling the compared length each round, then compute adjacent longest-common-prefixes with Kasai's algorithm. The pair answers substring search, distinct substring counting, and longest repeated substring. The log² build is plenty for n up to a few hundred thousand.
// use it on
SPOJ: SARRAY ↗
Output the suffix array itself. Building it is the entire problem.
// the code
// sa[i] = start of the i-th smallest suffix
vector<int> suffix_array(const string& s) {
int n = s.size();
vector<int> sa(n), rnk(n), tmp(n);
iota(sa.begin(), sa.end(), 0);
for (int i = 0; i < n; i++) rnk[i] = s[i];
for (int k = 1;; k <<= 1) {
auto cmp = [&](int a, int b) {
if (rnk[a] != rnk[b]) return rnk[a] < rnk[b];
int ra = a + k < n ? rnk[a + k] : -1;
int rb = b + k < n ? rnk[b + k] : -1;
return ra < rb;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i - 1]] + cmp(sa[i - 1], sa[i]);
rnk = tmp;
if (rnk[sa[n - 1]] == n - 1) break;
}
return sa;
}
// Kasai: lcp[i] = LCP of suffixes sa[i] and sa[i + 1]
vector<int> lcp_array(const string& s, vector<int>& sa) {
int n = s.size();
vector<int> rnk(n), lcp(max(0, n - 1));
for (int i = 0; i < n; i++) rnk[sa[i]] = i;
for (int i = 0, h = 0; i < n; i++) {
if (rnk[i] + 1 < n) {
int j = sa[rnk[i] + 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[rnk[i]] = h;
if (h) h--;
} else {
h = 0;
}
}
return lcp;
}