abc2

ABC2

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

Poveste si cerinta...

Alfabetul limbii Makako este compus din numai $3$ simboluri: $a, b si c$. Orice cuvant al acestei limbi este un sir format dintr-un numar finit de simboluri din alfabet (la fel ca in cele mai multe din limbile folosite in prezent). Totusi, nu orice insiruire de simboluri formeaza un cuvant cu sens. Conform dictionarului limbii Makako, numai anumite siruri de simboluri reprezinta cuvinte cu sens (in continuare, prin $cuvant$ vom intelege unul dintre aceste siruri de simboluri ce au sens). O particularitate a limbii Makako este ca oricare doua cuvinte au exact aceeasi lungime.
 
De curand s-a descoperit un text antic despre care se presupune ca ar fi scris intr-un dialect vechi al limbii Makako. Pentru a verifica aceasta ipoteza, oamenii de stiinta vor sa determine in ce pozitii din text se regasesc cuvinte din limba. Textul poate fi privit ca o insiruire de $L$ simboluri din alfabetul limbii Makako, in care pozitiile simbolurilor sunt numerotate de la $1$ la $L$. Daca un cuvant din limba se regaseste ca o insiruire continua de simboluri in cadrul textului, iar pozitia de inceput a acestuia este $P$, atunci $P$ reprezinta o pozitie candidat. Oamenii de stiinta doresc sa determine numarul pozitiilor candidat din cadrul textului.
 
Sa presupunem ca dictionarul limbii Makako ar contine doar urmatoarele $3$ cuvinte: $bcc$, $aba$ si $cba$, iar textul antic descoperit ar fi $cababacba$. La pozitiile $2$ si $4$ din text se regaseste cuvantul $aba$. La pozitia $7$ se regaseste cuvantul $cba$. Cuvantul $bcc$ nu se regaseste in text. Asadar, in text exista $3$ pozitii candidat.

h2. Date de intrare

...

Prima linie a fisierului de intrare $abc2.in$ contine textul antic ce trebuie analizat. Urmatoarele linii, pana la sfarsitul fisierului, contin fiecare cate un cuvant din dictionarul limbii Makako.

h2. Date de iesire

...

In fisierul de iesire $abc2.out$ veti afisa un singur numar reprezentand numarul de pozitii candidat ce se gasesc in cadrul textului antic.

h2. Restrictii

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

* Textul antic este alcatuit din cel mult $10 000 000$ de caractere.
* Dictionarul limbii Makako va contine cel mult $50 000$ de cuvinte.
* Cuvintele au o lungime de cel mult $20$ de caractere.
* Datorita dificultatii celor care au scris dictionarul de a lucra cu un numar atat de mare de cuvinte, este posibil ca unele cuvinte sa apara de mai multe ori in dictionar.

h2. Exemplu
table(example). |_. abc2.in |_. abc2.out |

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

|bbcabbabcba
abba
bbca
abcb
bbca
aaaa
|3|

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

2352