Как посчитать количество различных подстрок строки?
Дана строка до 10^5, нужно число различных подстрок. Перебор всех подстрок и складывание в set — O(n^2) по памяти, не лезет. Какие есть нормальные способы и какой проще написать на контесте?
2 ответа
Самый простой по коду способ — через суффиксный массив + LCP. Всего подстрок (с повторами) n(n+1)/2. Каждая различная подстрока считается ровно один раз как «новый префикс» некоторого суффикса в отсортированном порядке. Суффикс sa[i] приносит (n - sa[i]) - lcp[i] новых подстрок: его длина минус то, что уже было общим с предыдущим суффиксом.
long long count_distinct_substrings(const string& s) {
int n = s.size();
vector<int> sa = build_sa(s); // длина n+1 со стражем; пропустите страж
vector<int> lcp = build_lcp(/*...*/);
long long total = 0;
for (int i = 0; i < n; ++i) {
int suf = sa[i]; // индексы реальных суффиксов
total += (n - suf) - lcp[i];
}
return total;
}
Сложность — O(n log n) (доминирует построение SA), память O(n). Аккуратно с индексами из-за сторожевого символа.
Альтернатива — суффиксный автомат: сумма len[v] - len[link[v]] по всем состояниям даёт то же число за O(n). Код суфавтомата компактнее, чем SA+LCP, если вы его знаете.
Если строка маленькая (n до ~2000), можно тупо хешами: для каждой длины кладём хеши всех подстрок в unordered_set и считаем уникальные — O(n^2) время, O(n) память на длину. На контесте это быстрее написать, чем SA, когда ограничения щадящие. Но на 10^5 только SA+LCP или суфавтомат.