Количество вхождений подстрок в строку в O(N)
Мне было интересно, как посчитать количество вхождений каждой иглы в стоге сена за линейное время. Я думал, что буду использовать алгоритм Aho-Corasick, но я не хочу, чтобы сложность времени зависела от количества попаданий игл.
2 ответа
Используйте Rabin–Karp, если вы хотите найти набор строк и не хотите зависеть от количества вхождений. Его среднее / лучшее время выполнения O(n + m), но его худшее время O(нм), где n длина текста и m комбинированная длина шаблонов поиска.
Если вы хотите искать только одну строку, вы можете использовать Кнут-Моррис-Пратт со сложностью O(n + k), где n длина текста и k длина шаблона поиска.
Если вам нужно только общее количество вхождений (и вам самим нет дела до позиций), вы можете эффективно использовать Aho-Corasick. Давайте предположим, что мы в данный момент находимся в узле v, Сколько подстрок заканчивается в текущей позиции. Я утверждаю, что это точно количество терминальных узлов, достижимых из v по суффиксным ссылкам. Но суффиксные ссылки образуют дерево. Таким образом, нам нужно посчитать количество конечных вершин на пути от v к корню в дереве, образованном суффиксными ссылками. Мы можем сделать это в O(1) время с линейной предварительной обработкой (например, можно построить это дерево в явном виде и вычислить сумму на пути от корня до любой вершины за линейное время, используя один поиск в глубину). Мы также можем обработать вершины в правильном порядке (например, в порядке увеличения высоты) и сделать что-то вроде sum[v] += sum[suffix_link(v)], В этом случае нам даже не нужно создавать это дерево.
Этот алгоритм четко работает за линейное время с размером входных данных (мы строим автомат Aho-Corasick и вычисляем сумму по "путям суффиксных связей" за линейное время, а затем используем автомат, как мы обычно это делаем).