ghicit

Ghicit

== include(page="template/taskheader" task_id="ghicit") ==

Tu si cu Taranul jucati un joc neinteresant. Tu ai un sir de caractere mare. Taranul iti spune un alt sir de caractere, iar tu trebuie sa raspunzi ca mai repede daca sirul respectiv este sau nu o subsecventa a sirului tau. Taranul  iti pune multe intrebari si, fiindca esti informatician, te-ai gandit ca ar merge mai repede daca ai sti dinainte toate sirurile despre care te poate intreba. Inainte de a face toata acesta munca te-ar interesa numarul total de subsecvente distincte ale sirului tau, ca sa stii daca are sens sa te apuci de acesta treaba sau nu.

Tu si cu Taranul jucati un joc neinteresant. Tu ai un sir de caractere mare. Taranul iti spune un alt sir de caractere, iar tu trebuie sa raspunzi ca mai repede daca sirul respectiv este sau nu o subsecventa a sirului tau. Taranul iti pune multe intrebari si, fiindca esti informatician, te-ai gandit ca ar merge mai repede daca ai sti dinainte toate sirurile despre care te poate intreba. Inainte de a face toata acesta munca te-ar interesa numarul total de subsecvente distincte ale sirului tau, ca sa stii daca are sens sa te apuci de acesta treaba sau nu.

h2. Cerinta

* $1 ≤ lungimea sirului ≤ 50 211$
* $1 ≤ N ≤ 2 000 000 000$

* $sirul contine caractere avand codul ASCII intre 0 si 255 si se termina cu caracterul "sfarsit de linie" care nu trebuie luat in considerare$

* O subsecventa a sirului $s=s{~0~}s{~1~}s{~2~}...s{~k~}$ este formata din caractere consecutive ale sirului $s{~i~}s{~i+1~}...s{~j~}$ cu $0 ≤ i ≤j ≤ k$
* Sirul contine caractere avand codul ASCII intre $0$ si $255$ si se termina cu caracterul $'\n'$ (sfarsit de linie) care nu trebuie luat in considerare

h2. Exemplu

h3. Explicatie

Subsecventele sunt: a, b, ab, ba, aba, bab, abab

Subsecventele sunt: $a, b, ab, ba, aba, bab, abab$

== include(page="template/taskfooter" task_id="ghicit") ==

1850