*Subproblema 1*

Aceasta problema admite mai multe solutii, insa cea de complexitate optima se foloseste de un automat 'Aho-Corasick':http://www.infoarena.ro/problema/ahocorasick. Va rugam sa-l studiati inainte de a citi mai departe. Vom numi nod terminal un nod din Aho-Corasick in care se termina un cuvant din dictionar. Fiecare nod din automat va avea un vector dinamic $mathces$, o lista cu indici ai prefixelor din text pentru care cuvantul determinat de acest nod (mai precis de drumul de la radacina la acest nod) este sufix. Atunci cand 'trecem textul prin automat' incarcam fiecare indice i din text (care reprezinta prefixul care se termina la pozitia i) in vectorul $matches$ al nodului la care am ajuns la momentul respectiv. Acesta va fi cel mai lung prefix al unui cuvant din dictionar care este sufix al unui prefixului i al sirului. Pentru a afla toate prefixele din dictionar care sunt sufixe ale acestui prefix i, este suficient sa copiem continutul vectorului $matces$ al nodului curent in vectorii $matches$ ai nodurilor in care ajungem urmarind pointerul de nepotrivire _fail_. Putem scoate pozitiile de potrivire ale cuvintelor din vectorii _matches_ ale nodurilor terminale.

Aceasta problema admite mai multe solutii, insa cea de complexitate optima se foloseste de un automat 'Aho-Corasick':http://www.infoarena.ro/problema/ahocorasick. Va rugam sa-l studiati inainte de a citi mai departe. Vom numi nod terminal un nod din Aho-Corasick in care se termina un cuvant din dictionar. Fiecare nod din automat va avea un vector dinamic $mathces$, o lista cu indici ai prefixelor din text pentru care cuvantul determinat de acest nod (mai precis de drumul de la radacina la acest nod) este sufix. Atunci cand 'trecem textul prin automat' incarcam fiecare indice i din text (care reprezinta prefixul care se termina la pozitia i) in vectorul $matches$ al nodului la care am ajuns la momentul respectiv. Acesta va fi cel mai lung prefix al unui cuvant din dictionar care este sufix al prefixului i al sirului. Pentru a afla toate prefixele din dictionar care sunt sufixe ale acestui prefix i, este suficient sa copiem continutul vectorului $matces$ al nodului curent in vectorii $matches$ ai nodurilor in care ajungem urmarind pointerul de nepotrivire _fail_. Putem scoate pozitiile de potrivire ale cuvintelor din vectorii _matches_ ale nodurilor terminale.

Atentie ! Aici se poate cadea intr-o capcana. Problema garanteaza ca numarul de aparitii ale cuvintelor din dictionar in text nu depaseste 10^4^, dar problema nu garanteaza pentru numarul de aparitii ale prefixelor cuvintelor din dictionar.