*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 prefix 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 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.

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.
Daca avem textul T:          aaaaaaa
si un cuvant un dictionar C: aaaaaaa

numarul de aparitii ale lui C in T este 1 dar numarul de aparitii ale unui prefix al lui C in T este <tex>O(L^2^)</tex> unde L este lungimea lui C. Urmarind procedeul de mai sus putem da peste o explozie in vectorii $matches$, dimensiunea lor find de ordinul <tex>O(Nr.aparitii.cuvinte*L^2^)</tex>. Pentru a remedia acest lucru, vom mentine in fiecare nod o valoare booleana care ne spune daca urmarind pointerul _fail_ mai putem ajunge la un nod terminal. Daca aceasta valoare este false, nu mai copiem continutul vectorului _matches_ al nodului curent mai departe.

Numarul de aparitii ale lui C in T este 1 dar numarul de aparitii ale unui prefix al lui C in T este <tex>O(L^2^)</tex> unde L este lungimea lui C. Urmarind procedeul de mai sus putem da peste o explozie in vectorii $matches$, dimensiunea lor find de ordinul <tex>O(Nr.aparitii.cuvinte*L^2^)</tex>. Pentru a remedia acest lucru, vom mentine in fiecare nod o valoare booleana care ne spune daca urmarind pointerul _fail_ mai putem ajunge la un nod terminal. Daca aceasta valoare este false, nu mai copiem continutul vectorului _matches_ al nodului curent mai departe.

Pana acum avem complexitate <tex>O(N + Nr.cuvinte*L + Nr.aparitii.cuvinte*L)</tex>.