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

Question

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

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..

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

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

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

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

Answer 1

Вот единица с O (n) как сложность времени наихудшего случая.

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

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

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