Файл заголовка knuth_morris_pratt.hpp содержит реализацию алгоритма Кнута-Морриса-Пратта для поиска последовательностей значений.
Основная предпосылка алгоритма Кнута-Морриса-Пратта заключается в том, что, когда происходит несоответствие, в искомом шаблоне содержится информация, которая может быть использована для определения того, где может начаться следующий матч, что позволяет пропустить некоторые элементы корпуса, которые уже были изучены.
Он делает это, создавая таблицу из искомого шаблона с одной записью для каждого элемента в шаблоне.
Алгоритм был задуман в 1974 году Дональдом Кнутом и Воганом Праттом и независимо Джеймсом Х. Моррисом. Три из них опубликовали его совместно в 1977 году в журнале SIAM Journal on Computing http://citeseer.ist.psu.edu/context/23820/0
Однако алгоритм Кнута-Морриса-Пратта не может быть использован с такими предикатами сравнения, как std::поиск.
Номенклатура: Я называю последовательность, которую ищут, «паттерном», а последовательность, которую ищут, — «корпусом».
Для гибкости алгоритм Кнута-Морриса-Пратта имеет два интерфейса: объектный и процедурный. Объектный интерфейс строит таблицу в конструкторе и использует оператор () для выполнения поиска. Процессуальный интерфейс создает таблицу и выполняет поиск всего за один шаг. Если вы собираетесь искать один и тот же шаблон в нескольких корпусах, то вы должны использовать интерфейс объекта и строить таблицы только один раз.
Вот интерфейс объекта:
template <typename patIter>
class knuth_morris_pratt {
public:
knuth_morris_pratt ( patIter first, patIter last );
~knuth_morris_pratt ();
template <typename corpusIter>
corpusIter operator () ( corpusIter corpus_first, corpusIter corpus_last );
};
вот соответствующий процедурный интерфейс:
template <typename patIter, typename corpusIter>
corpusIter knuth_morris_pratt_search (
corpusIter corpus_first, corpusIter corpus_last,
patIter pat_first, patIter pat_last );
Каждая из функций передается двумя парами итераторов. Первые два определяют корпус, а вторые два определяют образец. Обратите внимание, что две пары не обязательно должны быть одного типа, но они должны «указать» на один и тот же тип. Другими словами, patIter::value_type и curpusIter::value_type должны быть одного и того же типа.
Обратное значение функции — итератор, указывающий на начало рисунка в корпусе. Если образец не найден, он возвращает конец корпуса (corpus_last).
Время выполнения алгоритма Кнута-Морриса-Пратта является линейным по размеру искомой строки. Как правило, алгоритм становится быстрее, поскольку искомый шаблон становится длиннее. Его эффективность обусловлена тем, что при каждой неудачной попытке найти соответствие между поисковой строкой и текстом, который он ищет, он использует информацию, полученную из этой попытки, чтобы исключить как можно больше позиций текста, где строка не может соответствовать.
Алгоритм a, который содержит одну запись для каждого элемента шаблона, плюс одну дополнительную. Так, при поиске 1026-байтовой строки таблица будет иметь 1027 записей.
Наихудшая производительность - O(2n), где n - длина корпуса. Среднее время составляет O(n). Лучшая производительность — сублинейная.
Как объектно-ориентированная, так и процедурная версии алгоритма Кнута-Морриса-Пратта берут свои параметры по значению и не используют никакой информации, кроме той, что передается. Таким образом, оба интерфейса обеспечивают сильную гарантию исключения.
- При использовании интерфейса, основанного на объекте, шаблон должен оставаться неизменным во время поиска; то есть с момента создания объекта до окончательного вызова оператора () возвращается.
- Алгоритм Кнута-Морриса-Пратта требует итераторов случайного доступа как для шаблона, так и для корпуса. Это должно быть возможно написать, чтобы использовать двунаправленные итераторы (или, возможно, даже вперед), но эта реализация не делает этого.
