2. TEN vtákopysk

Kaťa bola z vašej pomoci so šľachtením vtákopyskov veľmi nadšená. Dokonca až tak, že si zmyslela, že sa na celú problematiku pozrie aj s pomocou počítačov. Vymyslela si úžasné postupy, ako namiešať ten správny genetický koktejl, ktorým vznikne TEN vtákopysk.

Vtákopysk, ktorý prežije kúpanie sa v láve. Vtákopysk, ktorý prežije uviaznutie v kocke ľadu. Vtákopysk, ktorému sa budú zaceľovať rany. Predtým, ako vzniknú. Vtákopysk, ktorý …

Celé jej bádanie dorazilo až do štádia, v ktorom zistila, ako zhruba má vyzerať ten správny genóm. Identifikovala teda neveľa možností, z ktorých si potrebuje vybrať, samozrejme, tú najlepšiu, čiže takú, ktorá obsahuje čo najdlhší úsek genómu aspoň dvakrát (pričom oba výskyty sa môžu prekrývať).

Úloha

Dostanete reťazec pozostávajúci zo znakov A, C, G a T, potenciálny genóm ideálneho vtákopyska. Zistite, aký najdlhší súvislý podreťazec sa v ňom vyskytuje aspoň dvakrát.

Riešenie

Táto úloha je zaujímavá tým, že vám prezradíme, že sa dá riešiť využitím takzvaného sufixového poľa. Odporúčame vám naštudovať si, čo to sufixové pole je, na čo je dobré a ako sa programuje.

Časový limit je viac ako trojnásobok času optimálneho riešenia, ale máme aj riešenie s neoptimálnou časovou zložitosťou, ktoré dostane plný počet bodov.

Program a celý zdrojový kód, ktorý odovzdáte, však musí byť váš vlastný. Nemôžete napríklad skopírovať alebo odpísať nejaký cudzí kód sufixového poľa a odovzdať ho. Môžete si na internete pozrieť takéto kódy, ale potom musíte z vlastnej hlavy naprogramovať to, čo odovzdáte.

Formát vstupu a výstupu

Na prvom riadku dostanete číslo \(n\) (\(1 \leq n \leq 10^6\)), dĺžku reťazca. Na druhom riadku bude daný reťazec.

Vypíšte jedno číslo, dĺžku najdlhšieho súvislého podreťazca, ktorý sa v našom reťazci vyskytuje aspoň dvakrát.

Príklad

Input:

5
ACGAC

Output:

2

Najdlhší je reťazec AC.

Input:

4
ACGT

Output:

0

Nech budeme robiť, čo budeme robiť, nenájdeme neprázdny reťazec, ktorý sa nám bude vyskytovať viackrát.

Input:

5
AAAAA

Output:

4

Keďže sa naše reťazce môžu prekrývať, najdlhším bude AAAA.