E. Различные подстроки

Посчитайте количество различных непустых подстрок данной строки.

Хеши по длинам

Подстроки разной длины различны заведомо. Значит ответ - сумма по длинам $L$ количества различных хешей среди $n - L + 1$ кусков длины $L$:

Long answer = 0;
for (int len = 1; len <= n; len++) {
    std::unordered_set<Long> seen;
    for (int i = 0; i + len <= n; i++) seen.insert(sub(i, i + len - 1));
    answer += seen.size();
}

Это $O(n^2)$ вставок в множество. При $n = 2000$ - два миллиона, проходит.

Чем это отличается от таблицы lcp

В прошлом занятии та же задача решалась таблицей наибольших общих префиксов - тоже $O(n^2)$, но по памяти $O(n^2)$, а здесь $O(n)$. Разница видна как раз на границе: таблица при $n = 2000$ занимает 16 мегабайт, хеши - ничего.

Настоящее решение этой задачи - суффиксный массив с массивом lcp за $O(n \log n)$ или суффиксный автомат за $O(n)$. Ограничение здесь занижено намеренно: занятие про хеши.

Про unordered_set

unordered_set от long long при плохом раскладе деградирует до квадрата из-за предсказуемой хеш-функции. Надёжнее собрать все хеши в вектор, отсортировать и посчитать различные - это $O(n \log n)$ на длину без риска.

Подробнее: «Полиномиальное хеширование».

Одна строка из строчных латинских букв длиной не больше 2000.

Выведите количество различных непустых подстрок.