Можно ли посчитать количество различных подстрок в строке в O(n)?

Учитывая строку s длины nМожно ли посчитать количество различных подстрок в s в O(N)?

пример

Входные данные: abb

Выход: 5 ('abb', 'ab', 'bb', 'a', 'b')

Я провел некоторые исследования, но я не могу найти алгоритм, который решает эту проблему таким эффективным способом. Я знаю, что O(n^2) подход возможен, но есть ли более эффективный алгоритм?

Мне не нужно получать каждую из подстрок, просто общее количество отдельных (в случае, если это имеет значение).

Источник

2 ответа

Решение

Вы можете использовать алгоритм Укконена для построения дерева суффиксов за линейное время:

https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm

Количество подстрок s - это количество префиксов строк в дереве, которое вы можете вычислить просто за линейное время. Это просто общее количество символов во всех узлах.

Например, ваш пример создает дерево суффиксов, например:

            /\                
           b  a
           |  b
           b  b

5 символов в дереве, поэтому 5 подстрок. Каждая уникальная строка представляет собой путь от корневого окончания, заканчивающегося другой буквой: abb, ab, a, bb, b. Таким образом, количество строк - это количество букв в дереве.

Точнее:

  • Каждая подстрока является префиксом некоторого суффикса строки;
  • Все суффиксы в три;
  • Таким образом, существует соответствие 1-1 между подстроками и путями через три (по определению три); а также
  • Существует соответствие 1-1 между буквами в дереве и непустыми путями, потому что:
    • каждый отдельный непустой путь заканчивается в отдельной позиции после последней буквы; а также
    • путь к позиции, следующей за каждой буквой, уникален

ПРИМЕЧАНИЕ для людей, которые задаются вопросом, как можно построить дерево, содержащее O(N^2) символов за O(N):

Есть хитрость в представлении дерева суффиксов. Вместо того, чтобы хранить фактические строки в узлах дерева, вы просто сохраняете указатели в оригинальной строке, поэтому узел, содержащий "abb", не имеет "abb", он имеет (0,3) - 2 целых числа в узел, независимо от длины строки в каждом узле, а дерево суффиксов имеет O(N) узлов.

Источник

Построить массив LCP и вычесть его сумму из числа подстрок (n(n+1)/2).

Источник
Другие вопросы по тегам