The Postal Owl

1. **Špatný vstup pro naivní algoritmus**

    Nechť $s = a^n$ a $j = a^mc$

	Pak algoritmus poběží $(S-J)J = SJ-J^2 \in \Theta(SJ)$

2. **Nejdelší vlastní prefix**

    Projdeme slovo od začátku a zároveň od konce, končíme při neshodě znaků. Protože se musí jednat o vlastní prefix, nemůžeme vrátit délku celého slova, takže v případě palidromu snížíme délku o jednotku.  
    Prakticky můžeme k řetězci $\alpha$ sestrojit obrácený řetězec $\alpha_{rev}$. Z obou řetězců odstraníme poslední znak a pak vracíme délku shodných prefixů obou řetězců.
    Řetězec takto projdeme dvakrát, algoritmus je lineární. Pamětově je konstantní, protože až na vstup nic neukládáme.

3. **Příliš jehel**

	Uvažme seno $s = a^n$ kde BÚNO $n = 2^i, i \in \mathbb{N}$.  
	K němu uvažme jehly $\iota = \{ a, a^2, a^4, a^8, ..., a^n \}$
	
	Celková délka sena je $n$.
	Součet délek jehel $J = 1 + 2 + 4 + ... + n = 2n - 1 \in \Theta(n)$
	
	Ale celkový počet výskytů bude $n + (n-1) + (n-3) + (n-7) + ... + 1 = n \log(n) - const \cdot n$

4. **Počty výskytů jehel**

	Použijeme AC algoritmus, ale nebudeme procházet zkratkové hrany. Místo toho si v každém stavu automatu uložíme, kolikrát jsme se v něm zastavili. 
	Na konci projdeme celý strom automatu a vždy projdeme všechny zkratkové hrany, součty takto sečteme pro každou jehlu. Pak už zbývá jenom strom projít podruhé
	a pro každý vrchol s jehlou ohlásit počet výskytů. Tyto průchody jsou lineární s počtem jehel, každá zkratková hrana odpovídá jehle.

Díky, můžu to ještě do deadline opravit?

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.