The Postal Owl

2\. Mohli bychom to udělat třeba takto: Spustíme na retězci KMP, tj. jehla i seno budou stejný řetězec, na konci je automat v stavu nalezení jehly, podíváme se, kam z tohoto stavu vede zpětná hrana, ten stav bude příslušet části řetězce, která bude hledaným prefixem i suffixem. Nalezený stav bude odpovídat prefixu i suffixu, prefixu triviálně proto, že se jedná o prefix jehly, takový máme automat, suffixu proto, že se do tohoto stavu dostaneme skokem po zpětné hraně, a tak jsme ji dříve definovali, jako nejdelší vlastní suffix sena (řetězce), který je prefixem jehly (řetězce). Jedná se o suffix vlastní, tedy to bude i vlastní prefix - délka nebude rovna délce řetězce. 4\. Dovysvětlení průchodu stromem automatu. Na konci algoritmu projdeme celý strom, vrcholy seřadíme podle vzdálenosti od kořene od největší, vždy skočíme po případné zkratkové hraně a přičteme počet ve vrcholu k počtu v nově dosaženém vrcholu, dál neskáčeme, vezmeme další vrchol. Toto je lineární se součtem délek jehel, stejně jako stavba automatu, z každého stavu skočíme maximálně jednou, každý stav odpovídá písmenu v jehle. Toto bude fungovat, protože vždy, když skáčeme z nějakého vrcholu, už jsme na něj skočili všemi zkratkami - buď to není vrchol s koncem jehly - pak na něj žádná zkratka nevede, nebo je to vrchol s koncem jehly, ale pak všechny zkratky na něj vedoucí musí být ze stavů s delším řetězcem stavu. Na konci projdeme celý strom a pro vrcholy s konci jehel ohlásíme daný počet, lineární s délkami jehel, nebo s počtem jehel, pokud si předem na tyto vrcholu uchováme odkazy.

Preview