Поиск одинаковых подстрок в строке?

Может быть кто-то сталкивался с алгоритмами поиска одинаковых подстрок в строке. Например, есть строка «1234567845690450», мы устанавливаем, что нам интересны подстроки 3 и более символов, в результате надо найти подстроку «456» т.к. она встречается в строке более одного раза.


Как сделать это в лоб медленно ясно — но надо быстро.
  • Вопрос задан
  • 17216 просмотров
Решения вопроса 1
@al13n321
Copy-paste detector есть в PMD: pmd.sourceforge.net/pmd-5.0.1/cpd.html (не нашел сходу нормального описания на их сайте; когда-то видел статью про то, как он устроен: там суффиксный массив).

Если нужен именно алгоритм, то за O(N log N) (или, если постараться, O(N)) в худшем случае можно использовать суффиксный массив, суффиксное дерево или суффиксный автомат (осторожно, статьи ориентированы на спортивное программирование, стиль кода может быть непривычным).

Пожалуй, проще всего работать с суффиксным массивом: это просто все суффиксы строки, упорядоченные в лексикографическом порядке (конечно, сами суффиксы хранятся не как строки, а как индексы начала). Для всех пар соседних суффиксов можно быстро найти LCP (наибольший общий префикс). Пусть дана минимальная длина (назовем ее L) искомых подстрок. Если в суффиксном массиве нашлись K последовательных (в лексикографическом порядке) суффиксов таких, что LCP любых двух соседних не меньше L, то LCP их всех есть подстрока исходной строки, входящая в нее хотя бы K раз. Используя эту идею, за O(N log N) можно, например, найти все подстроки длины L, встречающиеся хотя бы K раз (хотя это проще сделать хешами, как предложил mihaildemidoff). Наверно, можно аналогично перебирать подходящие строки в порядке убывания длины или количества вхождений. Но наверно это удобнее делать суффиксным деревом.

Наверно, прямо при построении суффиксного дерева можно для каждой вершины найти количество вхождений соответствующей ей подстроки. Таким образом, мы найдем вообще для каждой подстроки количество ее вхождений. Но чтобы получилось O(N), а не O(N^2) данных, подстроки будут разбиты на группы (соответствующие вершинам дерева) с одинаковым количеством вхождений, и все произойдет за O(N). Того же самого можно (проще в реализации и сложнее в понимании) добиться и суффиксным автоматом (он в некотором смысле двойственен суффиксному дереву). Такой конструкции, наверно, достаточно для решения поставленной задачи в любой разумной конкретной формулировке.
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
@mihaildemidoff
Как вариант можно посчитать хэши подстрок нужной длины, после этого отсортировать их. Еще за один проход мы найдем максимальное число повторений одного хэша, еще за один проход в строке найдем исходную подстроку(хотя можно сразу же хранить).
Ответ написан
KEKSOV
@KEKSOV
Один из простых вариантов — построение частотного словаря. Более сложный вариант двоичное упорядоченное дерево. Примеры применения в статье про LZW или в статье про сжатие изображений
Ответ написан
Комментировать
VBart
@VBart
Смотрите реализации алгоритма LZ77 во всяких gzip-ах.
Ответ написан
Комментировать
elw00d
@elw00d
7-zip в LZMA использует метод цепочек хешей. Видимо, это самый быстрый метод, т.к. в ранних версиях LZMA SDK было 3 реализации поиска совпадений: hash chains, binary search tree, patricia tree. А теперь осталась только одна. Алгоритмы, основанные на деревьях, были выброшены. Как работает каждый из этих методов, можно прочитать в википедии
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы