Последовательное точное сравнение строк: различия между версиями

Пусть даны ''строка шаблона'' <math>P = p_1 p_2 ... p_m</math> и ''текстовая строка'' <math>T = t_1 t_2 ... t_n</math>, представляющие собой последовательности над алфавитом <math>\Sigma</math> размера <math>\sigma</math>. Задача ''точного сравнения строк'' (exact string matching, ESM) заключается в нахождении одной или, в общем случае, всех текстовых позиций, в которых P входит в T; иначе говоря, в вычислении множества <math> \{ j | 1 \le j \le n - m + 1, P = t_j t_{j + 1} ... t_{j + m - 1} \} </math>. Предполагается, что шаблон задается первым, после чего производится поиск его вхождения в нескольких текстах.