Подсчет количества подстрок

Question

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

Answer 1

[РЕДАКТИРОВАНИЕ 17/11/2013: количество листьев узлов. Спасибо Виниций Пинто!]

Вы можете построить дерево суффиксов для текста за линейное время. Затем найдите вашу подстроку в дереве суффиксов; когда вы его найдете, посчитайте количество листовых узлов под соответствующим узлом. Это O (m + k) для подстроки длиной m, которая появляется k раз (добавьте n член для построения дерева суффиксов). Или вы можете предварительно рассчитать количество потомков для каждого узла в дереве, используя обход в глубину - это даст O (m) запросов.

Для больших текстов суффиксные массивы часто быстрее, чем суффиксные деревья на практике, несмотря на поиск единственной строки длиной m, опускающейся с O (m) до O (m log m). В этом случае все вхождения конкретной подстроки будут отображаться как непрерывный блок в массиве суффиксов, поэтому ширина этого блока равна числу вхождений.

Answer 2

Вы можете использовать алгоритм KMP и изменить его, чтобы увеличить счетчик вместо возврата.

Другой возможностью является алгоритм Рабина-Карпа , однако он основывается на хешировании, поэтому вы должны либо принять вероятность ложных срабатываний, сохраняя сложность линейной, либо принять возможность квадратичной сложности, сохраняя результаты на 100% правильные.