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

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: решебник по русскому класс, темы рефератов по физике
| Добавил(а) на сайт: Nyrkov.

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 класс контрольные работы, шпоры по химии, доклад на тему.