Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта (КМП) получает на вход слово.Что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C.Описать алгоритм заполнения.Алгоритм Бойера - Мура.Предположим, что первые i значений l [1] ...l [i] уже найдены.Мы читаем очередную букву слова (т.е. x [i+1]) и должны вычислить l [i+1] .Откуда берутся эти начала?Как так может быть?Как заполнить массив pos?Вначале last=n (длина образца) , затем last постепенно увеличивается.