[Править]Алгоритм

Алгоритм начинается с подсчета   и  .

Для   вычисляется   и сравнивается с  . Если они оказались равны, то образец   скорее всего содержится в строке  начиная с позиции  , хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.

Для ускорения работы алгоритма оптимально предпосчитать  .

[Править]Псевдокод

RabinKarp (s[1..n], p[1..m])

hp = hash(p[1..m])

h = hash(s[1..m])

for i = 1 to n - m + 1

if h == hp

answer.add(i)

h = (p * h - p * hash(s[i]) + hash(s[i + m])) mod r

if answer.size() == 0

return not found

else

return answer

Новый хеш   был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что   — пустой символ.

[Править]Время работы

Изначальный подсчёт хешей выполняется за  . В цикле всего   итераций, каждая выполняется за  . Итоговое время работы алгоритма  .

[Править]Надёжность

Если количество подстрок данной строки превышает количество хешей, то наступление коллизий неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть высока, не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.

Например если взять  , за   принять строку Туэ-Морса^[1] длиной   , то алгоритм находит лишние вхождения почти в половине случаев.

    Конечный автомат (состояния, начальное сост., допускающее сост., входной алфавит, функция переходов)

Конечный автомат — абстрактный автомат, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

Существуют различные способы задания конечного автомата. Например, конечный автомат может быть задан в виде упорядоченной пятерки:  , где

•  — входной алфавит (конечное множество входных символов), из которого формируются входные цепочки, допускаемые конечным автоматом;

•  — множество состояний;

•  — начальное состояние  ;

•  — множество заключительных состояний  ;

•  — функция переходов, определенная как отображение  , такое, что  , то есть значение функции переходов на упорядоченной паре (состояние, входной символ или пустая цепочка) есть множество всех состояний, в которые из данного состояния возможен переход по данному входному символу или пустой цепочке (λ).

Конечный автомат начинает работу в состоянии q₀, считывая по одному символу входной цепочки. Считанный символ переводит автомат в новое состояние в соответствии с функцией переходов. Читая входную цепочку x и делая один такт за другим, автомат, после того как он прочитает последнюю букву цепочки, окажется в каком-то состоянии q'. Если это состояние является заключительным, то говорят, что автомат допустил цепочку x.

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

Работа КА заключается в преобразовании входной цепочки символов в выходную. Закон этого преобразования определяет поведение КА. Задача проектирования КА состоит в создании КА, обеспечивающем заданные правила преобразования цепочек. Очевидно, что отсутствие у КА внутренней памяти ограничивает его возможности по преобразованию цепочек (общепринятый термин -моделирующая способность). С другой стороны, эти же ограничения позволяют решать в общем случае многие проблемы (термин – алгоритмическая разрешимость, т.е. принципиальная возможность разработать соответствующий алгоритм).

Хотя автоматы и можно представить в традиционной для алгоритма технологии блок-схем (управляющие КА так и строятся на основе разметки блок-схемы алгоритма), наиболее удобной формой их представления для человека является графическая - диаграмма состояний-переходов, а для программирования и формальных преобразований – табличная. Основные элементы диаграммы состояний – переходов:

• состояние представляет собой окружность, содержащую номер или наименование состояния;

• направленная дуга, соединяющая состояния S_k и S_m, определяется значениями функций переходов и действий: если  S_m=P(S_k,I_i) и O_n=D(S_k,I_i), то имеется переход КА из  S_k вS_m , который обозначается дугой, соединяющей эти вершины. Дуга подписывается парой символов I_i/O_n . Это означает, что переход по дуге при поступлении на вход символа I_iсопровождается  формированием выходного символа O_n.

Если поведение какого-либо объекта можно описать набором предложений вида: «Находясь в состоянии A, при получении сигнала S объект переходит в состояние B и при этом выполняет действие D», то такая система будет представлять собой конечный автомат.

Анализируя приведенный здесь пример диаграммы состояний-переходов и вид преобразования цепочек, можно сделать вывод о поведении автомата и сущности выполняемых им преобразований. Нетрудно заметить, что получая входные цепочки, содержащие символы a и b в произвольном порядке, КА формирует аналогичные цепочки более регулярного вида. Так, из подряд идущих символов b он оставляет один, а в последовательности символов a оставляет все нечетные, кроме первого. При нечетном количестве символов a на входе КА добавляет еще один символ a в выходную последовательность.  Отсюда можно вычислить закон преобразования длины входной цепочки символов a  -  N_a(out) = (N_a(in)+1)/2

Анализируя состояния и условия переходов в них, можно определить их содержательный «смысл»: состояния S_{1 ,}S₂ обозначают нечетное и четное число подряд прочитанных символов a. 

Табличная форма представления КА включает в себя представление функций переходов и выходов виде таблиц.

 

P	a	b
S0	1	0
S1	2	0
S2	1	0

 

D	a	b
S0	b	e
S1	e	a
S2	a	e

На диаграмме состояний-переходов не может быть двух и более дуг из одного состояния, помеченных одним и тем же входным символом.  Если это не так, то такая неканоническая форма называется недетерминарованным КА. Такой КА не имеет адекватного табличного (функционального) представления, но может быть преобразован в обычный детерминированный.