Problema seti,Campion 2009

Vasile este convins ca nu suntem singuri in Univers. In fiecare seara el inregistreaza semnale venite din spatiu si le memoreaza sub forma unui sir T format din litere ale alfabetului latin. Pentru a decodifica mesajele primite din spatiu, Vasile utilizeaza un sir auxiliar P asupra caruia efectueaza urmatoarele operatii:
A: adauga un caracter la sfarsitul sirului P
Q: afla de cate ori sirul P apare ca subsecventa a sirului T.
Initial sirul P este vid.

Cerinta

Scrieti un program care, cunoscand mesajul T si operatiile efectuate de Vasile asupra sirului P, afiseaza raspunsul la operatiile de tip Q.

Date de intrare

Fisierul de intrare seti.in contine pe prima linie mesajul T. Pe cea de a doua linie sun descrise operatiile pe care le efectueaza Vasile, sub forma unui sir de caractere. Al i-lea caracter din acest sir este o litera (semnificand faptul ca Vasile adauga litera respectiva la sfarsitul sirului P) sau un ? (semnificand o operatie de tip Q).

Date de iesire

Fisierul de iesire seti.out va contine cate o linie pentru fiecare operatie de tip Q, linie pe care va fi scris raspunsul (de cate ori sirul P apare ca subsecventa a sirului T).

Restrictii

• Åžirul T contine cel mult 200 000 litere ale alfabetului latin.
• Vasile executa cel mult 200 000 de operatii.
• Åžirul P nu incepe cu caracterul ‘?’.

Exemple

seti.in	seti.out
mamamamaiasieulaMamaia ma?ma?i?e?	5 3 1 0

Solutia mea

Aceasta problema este o aplicatie directa a algoritmului de cautare a unui subsir intr-un alt sir,sau algoritmul lui Knuth-Morris-Pratt(KMP) ce va fi prezentat curand si pe blog.Trebuie citit normal sirul A(primul sir), iar in al doilea se vor elimina intrebarile.Construirea prefixului noului sir B se va face clasic.Rezolvarea in sine are loc la modificarea algoritmului de determinare a unui subsir intr-un sir.Cei care cunosc algoritmul KMP stiu ca el determina practic cel mai lung prefix ce l-a gasit pana la un moment dat.Astfel de vom folosi de aceasta informatie si vom avea sol[q]++ (vom adauga un prefix de lungime q la lista celor existente deja).Generarea vectorului de solutii(practic generarea tuturor solutiilor pentru orice prefix de lungime <= m se va face in momentul in care vom adauga sol[i] la sol[pi[i]], pi[i] fiind prefixul sirului B.Urmeaza afisarea rezultatelor in functie de intrebari.Acest algoritm va avea complexitate aproape liniara(N+2M+k), N = strlen(A),M=strlen(B), k = strlen(intrebari).
Descarcati solutia pentru problema seti de la Campion 2009.