Дана строка. Посчитайте, сколько у неё различных непустых подстрок
(подстрока — непрерывный кусок строки).
// CountDistinctSubstrings возвращает число различных непустых подстрок s.
func CountDistinctSubstrings(s string) int
Примеры
"CCCCC" → 5 // C, CC, CCC, CCCC, CCCCC
"ABABA" → 9 // A B AB BA ABA BAB ABAB BABA ABABA
"ABC" → 6
"" → 0
Ограничения
0 ≤ len(s) ≤ 10⁵. Строка — произвольные байты (сравнение побайтовое).- Подстрок порядка n²/2 ≈ 5·10⁹ — перебрать их не получится. Ожидается
O(n log n) или O(n log² n).
Устно: через какую структуру данных ещё решается эта задача? Как найти
число различных подстрок фиксированной длины k?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.