Как достичь "подстрочного соответствия" в O (n) времени?

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

Adana 
Izmir Adnan Menderes Apt
Addis Ababa
Aden
ADIYAMAN
ALDAN
Amman Marka Intl Airport
Adak Island
Adelaide Airport
ANURADHAPURA
Kodiak Apt
DALLAS/ADDISON
Ardabil 
ANDREWS AFB
etc..

Если я укажу поисковый запрос, программа должна найти строки, в которых происходит подстрока. Например, если поисковый запрос "uradha", программа должна показывать ANURADHAPURA. Если поисковый термин "аэропорт", программа должна показать Amman Marka Intl Airport, Adelaide Airport

Цитата из спецификаций присваивания: "Вы должны запрограммировать это приложение на эффективность, учитывая, что задействованы большие объемы данных и обработка".

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

Мне было интересно, какие решения существуют, что дает производительность лучше, чем O (n)?

Ответ 1

Вы можете взглянуть на алгоритм строкового поиска Boyer-Moore или строчный алгоритм поиска Knuth-Morris-Pratt. Они имеют хорошую асимптотическую производительность, но я не знаю алгоритма, который не требовал бы, по крайней мере, считывать один раз (почти все) как входную, так и выходную строку и, следовательно, был бы лучше, чем производительность O (n) (где n - размер ввода).

Ответ 2

Ниже приведено значение 1 с O (n) как наихудшая временная сложность.

Кстати, вы должны пометить эту ссылку: http://www-igm.univ-mlv.fr/~lecroq/string/

Ответ 3

Моя кишка говорит, что вы на правильном пути, думая о trie, и вы можете изучить этот раздел на странице Wikipedia, который ссылается на Суффикс Дерево для некоторых других идей. O (n), к сожалению.

Ответ 4

Текст ввода имеет почти статический контент (или значения добавляются не так часто, а значения добавляются в конец источника ввода), но поиск часто можно попробовать (возможно, так же, как и trie)

1) Вы прочтете весь текст (а также обновите, затем добавит новый элемент) и подготовьте таблицу индексов (карта символа для координации (строка или строка с позицией), где происходит совпадение)

'aa' - 1, 15, 27... 
'as' - 1, 15, 17...
'ba' - 2, 3, 15...
...

2) Первая координата поиска в индексной таблице с помощью первых двух символов

3) Затем продолжите поиск в тексте ввода по координатам

Ответ 5

Boyer-Moore и несколько алгоритмов, которые используют варианты для некоторых своих идей, могут достичь "O (n/m)" (где n - длина стога сена, а m - длина иглы). некоторые иглы, но это зависит от критериев повторения на игле, которые невозможно удовлетворить для сколь угодно больших m (например, когда m становится намного больше размера набора символов), что делает даже лучшие случаи чем-то более похожим на O (n/256 ) и, следовательно, O (n). Тем не менее в реальных приложениях, где m имеет тенденцию быть маленьким, и иглы, как правило, не являются патологически-периодическими, BM и его кузены могут работать очень хорошо.

Лично я рекомендую алгоритм "Two Way" (с BM-подобными расширениями, используемыми в реализации glibc), за то, что он гарантировал O (n) границы и постоянное рабочее пространство.