Алгоритм Кнута - Морриса - Пратта
Категория реферата: Рефераты по информатике, программированию
Теги реферата: решебник по русскому класс, темы рефератов по физике
Добавил(а) на сайт: Nyrkov.
Предыдущая страница реферата | 1 2
while (x[len+1]х[i+1]) and (len>0) do begin
{начало не подходит, применяем к нему функцию l}
len:=l[len];
end;
{нашли подходящее или убедились в отсутствии}
if x[len+1]=x[i+1] do begin
{х[1]..x[len] - самое длинное подходящее начало}
l[i+1]:=len+1;
end else begin
{подходящих нет}
l[i+1]:= 0;
end;
i:=i+1;
end;
Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C.
Решение. Это не вполне очевидно: обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l[i+1] окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием.
Более точно, можно записать неравенство
l[i+1]
Скачали данный реферат: Mjachin, Prov, Anufriev, Евстолия, Radoslava, Рутберг, Ильина.
Последние просмотренные рефераты на тему: лечение шпори, 6 класс контрольные работы, шпоры по химии, доклад на тему.
Предыдущая страница реферата | 1 2