Etichete : .campion, algoritmica, informatica, OJI, ONI, Probleme algoritmica, seti

Vasile este convins că nu suntem singuri în Univers. În fiecare seară el înregistrează semnale venite din spaţiu şi le memorează sub forma unui şir T format din litere ale alfabetului latin. Pentru a decodifica mesajele primite din spaţiu, Vasile utilizează un şir auxiliar P asupra căruia efectuează următoarele operaţii:
A: adaugă un caracter la sfârşitul şirului P
Q: află de câte ori şirul P apare ca subsecvenţă a şirului T.
Iniţial şirul P este vid.

Cerinţă

Scrieţi un program care, cunoscând mesajul T şi operaţiile efectuate de Vasile asupra şirului P, afişează răspunsul la operaţiile de tip Q.

Date de intrare

Fişierul de intrare seti.in conţine pe prima linie mesajul T. Pe cea de a doua linie sun descrise operaţiile pe care le efectuează Vasile, sub forma unui şir de caractere. Al i-lea caracter din acest şir este o literă (semnificând faptul că Vasile adaugă litera respectivă la sfârşitul şirului P) sau un ? (semnificând o operaţie de tip Q).

Date de ieşire

Fişierul de ieşire seti.out va conţine câte o linie pentru fiecare operaţie de tip Q, linie pe care va fi scris răspunsul (de câte ori şirul P apare ca subsecvenţă a şirului T).

Restricţii

• Şirul T conţine cel mult 200 000 litere ale alfabetului latin.
• Vasile execută cel mult 200 000 de operaţii.
• Şirul P nu începe cu caracterul ‘?’.

Exemple

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.

Recomandam, pe aceeasi tema

Despre autorul articolului :

Avădănei Andrei - Autorul a scris 626 articole (vezi lista completa).

Contact | andrei[at]worldit[dot]info | @worldIT – @AndreiAvadanei

Fondator si redactor worldit.info, ma numesc Andrei si sunt pasionat de programare , in special de algoritmica si web development. Forumul WorldIT iti sta la dispozitie daca ai nevoie de suport tehnic, informatii si sugestii privind diverse produse prezentate pe blog si nu numai. Mai multe detalii despre activitatile mele aici.