OHW

Nepovinná domáca úloha

A (2 body)

Uvažujme Morissov-Prattov algoritmus pre vzorku P dĺžky m, ktorý bežíme na veľmi dlhom texte T. Koľko najviac bude trvať spracovanie úseku dĺžky k niekde uprostred textu T ako funkcia parametrov m a k? Hodnota k môže byť menšia alebo väčšia ako m. Uveďte aszmptotický horný aj dolný odhad, t.j aj príkald, kde to bude trvať