Статья 2291

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