Эффективный алгоритм поиска совпадений строк

Question

Я не буду вдаваться в детали проблемы, которую пытаюсь решить, но она имеет дело с большой строкой и включает в себя нахождение перекрывающихся интервалов, которые существуют в строке.Я могу использовать только один из перекрывающихся интервалов, поэтому я хотел выделить эти интервалы и проанализировать их по отдельности.Мне было интересно, какой алгоритм использовать, чтобы сделать это максимально эффективно.

Я должен подчеркнуть, что скорость здесь имеет первостепенное значение.Мне нужно разделить интервалы как можно быстрее.Алгоритм, который мне пришёл в голову, был Interval Tree, но я не был уверен, что это лучшее, что мы можем сделать.

Деревья интервалов могут запрашиваться за время O (log n), n - это количество интервалов, а для построения требуется время O (nlog n), хотя я хотел знать, можем ли мы сократить их либо.

Спасибо!

Редактировать: Я знаю, что вопрос неопределенный.Я прошу прощения за путаницу.Я предлагаю, чтобы люди посмотрели на ответ Аарона Хурана и комментарии к нему.Это должно помочь прояснить ситуацию намного больше.

Answer 1

Ну, мне было скучно прошлой ночью, поэтому я сделал это на Python.Это излишне рекурсивно (я только что прочитал «Маленький мошенник» и думаю, что рекурсия сейчас очень аккуратна), но оно решает вашу проблему и обрабатывает весь вводимый мной текст.1005 *

Обратите внимание, что он возвращает все перекрывающиеся интервалы в обратном порядке их начальной точки.Надеюсь, это небольшая проблема.Это происходит только потому, что я использую push() и pop() в списке, который работает в конце списка, а не insert(0) и pop(0), который работает в начале.

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

Answer 2

Вы можете попробовать использовать алгоритм Укконена (см. https://en.wikipedia.org/wiki/Ukkonen%27s_algorithm).

. Есть бесплатная версия кода на http://biit.cs.ut.ee/~vilo/edu/2002-03/Tekstialgoritmid_I/Software/Loeng5_Suffix_Trees/Suffix_Trees/cs.haifa.ac.il/shlomo/suffix_tree/suffix_tree.c

Answer 3

Вы хотите рассчитать разницу между двумя строками, верно? На каком языке вы пытаетесь это сделать?

Обновление: Без каких-либо критериев того, как вы будете выбирать, какие интервалы использовать, есть огромные возможные решения.

Один из методов - взять наименьшее начальное число и взять его конец. Возьмите следующий начальный номер, который выше конца предыдущего интервала. Получить конец этого интервала и повторить.

Так для 0-4, 5-13, 8-19, 10-12 Вы получаете: 0-4, 5-13 и игнорируете других.