Цитата: "Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово X=x[1]x[2]... x[n] и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l[1]... l[n], где l[i]=длина слова l(x[1]...х[i]) (функция l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала слова x[1]...x[i], одновременно являющегося его концом. Какое отношение все это имеет к поиску подслова? Другими словами, как использовать алгоритм КМП для определения того, является ли слово A подсловом слова B? Решение. Применим алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A. Описать алгоритм заполнения таблицы l[1]...l[n]. Решение. Предположим, что первые i значений l[1]...l[i] уже найдены. Мы читаем очередную букву слова (т.е. x[i+1]) и должны вычислить l[i+1]. ".

Скачать