Сколько разных подстрок в строке?

Question

Мне нужно разработать алгоритм в O (n), который задал строку t длины n, вычислить количество различных подстрок t.

Answer 1

1. Создайте автомат суффикса для входной строки.

2. Найти сумму maxLength[v] - maxLength[suffixLink[v]] for all states v, где maxLength[v] находится самый длинный путь от корня до v состояния и suffixLink[v] является ссылкой суффикса этого состояния.

Построение автомата суффикса в линейном времени является хорошо известной задачей. Вторая часть - просто простой обход. Таким образом, общая временная сложность составляет O(n).