Пусть $$ X=(x_1,\dots,x_n) , Y=(y_1,\dots,y_m) $$ — бинарные векторы. Проблема сопоставления строк (string matching problem)— это проблема нахождения одного или нескольких индексов $ i $ таких, что $$ X=Y_i:=(y_i,y_{i+1},\dots, y_{i+n-1}) \, . $$ В случае наличия такого $ i $ будем говорить, что сопоставление установлено. Задача: построить алгоритм, который устанавливает факт сопоставления с вероятностью, меньшей наперед заданного $\varepsilon > 0 $. Пусть $ p $ — наименьшее простое число, такое, что $$ p>\log_2\left(\frac{nm}{\varepsilon} \right) \, . \qquad {\color{Red}{ (1)} } $$ Пусть $$ a(t):=x_1t^{n-1}+\dots+x_n, \ a_i(t):=y_it^{n-1}+\dots+y_{i+n-1} \quad \mbox{при} \ i \in \{1,\dots,m+n-1\} \, . $$ Очевидно, сопоставление происходит при $ a(t)\equiv a_i(t) $.

Выбираем случайным образом неприводимый над $ \mathbb Z_2 $ полином $$ f(t)=t^{p}+b_1t^{p-1}+\dots+b_p \, . $$ Число таких полиномов — $$ \frac{1}{p} (2^p-2) \, , $$ (см. ☞ теорему 4 ).

Обозначим $$ \overline{g(t)}:= g(t) \mod f(t) \, , $$ т.е. остаток от деления $ g(t) $ на $ f(t) $, ну еще и коэффициенты потом по $ \mod 2 $ приведем. Вычисляем $$ \overline{a(t)}, \overline{t^{n-1}}, \overline{a_1(t)} \, . $$ Если $\overline{a(t)} = \overline{a_1(t)} $, то сопоставление происходит при $ i=1 $. На шаге $ i $ сохраняются полиномы $$ \overline{a(t)}, \overline{t^{n-1}}, \overline{a_i(t)}, f(t) \, , $$ задаваемые $ p $-разрядными векторами. Вычисляется $$ \overline{a_{i+1}(t)}:=( \overline{a_i(t)} + y_i \overline{t^{n-1}}) t + y_{i+n} \mod f(t) \, . \qquad {\color{Red}{ (2)} } $$

Если $\overline{a(t)} = \overline{a_{i+1}(t)} $, то соответствие установлено при $ i+1 $.

Теорема. Вероятность того, что приведенный алгоритм выдаст $ \ge 1 $ ошибки, не превосходит $ \varepsilon $. Более того, алгоритм обнаружит все сопоставления.

Пример. $ n=10^3, m=10^6, \varepsilon = 2^{-30}$, $ p=61 $ удовлетворяет неравенству $ {\color{Red}{ (1)} } $.

[1]. Rabin M.O. Fingerprinting by random polynomials. Technical report, 1981 .

.