418
правок
Изменения
м
==Асимптотики==
* Фаза предварительных вычислений требует <tex>O(m + \sigma)</tex> времени и памяти
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
* В лучшем случае требует <tex>O(n / m)</tex> сравнений.
В 1991 году Р.Коул доказал следующую теорему:
{{Теорема
|author=Richard Cole
|statement=В худшем случае требуется <tex>O(3 \cdot n)</tex> сравнений в случае шаблона с периодом равным длине самого шаблона.
|proof=Доказательство [http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps]
}}
* Сравнение не является "чёрным ящиком", поэтому при реализации наиболее быстрого поиска приходится либо рассчитывать на удачную работу оптимизатора, либо вручную оптимизировать поиск.
Нет описания правки
Алгоритм Бойера-Мура, разработанный двумя учеными – {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличии от многих других алгоритмов.
Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.
==Алгоритм==
Алгоритм сравнивает символы ''шаблона'' (<tex>y</tex>) справа налево, начиная с самого правого, один за другим с символами ''исходной строки'' (<tex>x</tex>). В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо.
Пусть <tex>|y|=n</tex> и <tex>|x|=m</tex>.
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
==Асимптотики==
* Фаза предварительных вычислений требует <tex>O(m + \sigma)</tex> времени и памяти
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
* В лучшем случае требует <tex>O(n / m)</tex> сравнений.
В 1991 году Р.Коул доказал следующую теорему:
{{Теорема
|author=Richard Cole
|statement=В худшем случае требуется <tex>O(3 \cdot n)</tex> сравнений в случае шаблона с периодом равным длине самого шаблона.
|proof=Доказательство [http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps]
}}
==Сравнение с другими алгоритмами==
===Недостатки===
* Алгоритмы семейства Бойера-Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.
* На больших алфавитах (например, Юникод) может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.
* На искусственно подобранных неудачных текстах (например, needle=«колоколоколоколоколокол»шаблон "abcabcabcabcabc") скорость алгоритма Бойера-Мура серьёзно снижается.
==Ссылки==
