ghicit

Ghicit

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

Poveste si cerinta...

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
 
Scrieti un program care afla numarul de subsecvente distincte ale unui sir de caractere dat.

h2. Date de intrare

...

Fisierul de intrare $ghicit.in$ contine pe prima linie sirul de caractere pentru care trebuie sa determinam numarul de subsecvente distincte.

h2. Date de iesire

...

Fisierul de iesire $ghicit.out$ contine o singura linie pe care se afla numarul $N$, reprezentand numarul de subsecvente distincte determinat.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ lungimea sirului ≤ 50 211$
* $1 ≤ N ≤ 2 000 000 000$
* 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
table(example). |_. ghicit.in |_. ghicit.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| abab
| 7

|
h3. Explicatie

...

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

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

1850