Fişierul intrare/ieşire:	strmatch.in, strmatch.out	Sursă	ad-hoc
Autor	Arhiva Educationala	Adăugată de	Banu Denis Andrei •DenisONIc
Timp execuţie pe test	0.15 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Potrivirea sirurilor

Se dau doua siruri A si B. Se cere gasirea tuturor aparitiilor sirului A ca subsecventa a sirului B.

Date de intrare

Fisierul de intrare strmatch.in contine 2 linii cu sirurile A, respectiv B.

Date de iesire

In fisierul de iesire strmatch.out se va afla pe prima linie numarul N de aparitii a sirului A in sirul B. Pe urmatoarea linie se vor afla N numere care reprezinta pozitiile in care sirul A se potriveste peste sirul B, afisate in ordine crescatoare. Sirurile sunt indexate de la 0.

Restrictii

• Lungimea sirurilor A si B se afla in intervalul [1, 1048575]

Exemplu

Explicatie

Cele doua aparitii sunt:

• CABBCABABAB
• CABBCABABAB

Cum se trimit solutii?

Indicatii de rezolvare

Problema se poate rezolva in complexitate O(|A| * |B|), incercand pe rand toate pozitile i in care sirul A se poate potrivi peste sirul B si comparand sirul A cu subsecventa de pe pozitia i din sirul B in complexitate O(|A|). Aceasta rezolvare obtine 40 de puncte.

Complexitatea optima pentru aceasta problema este O(|A| + |B|) si problema se poate rezolva cu ajutorul algoritmului KMP prezentat in acest articol de pe infoarena sau cu ajutorul algoritmului Rabin-Karp prezentat aici.

O solutie de 100 de puncte, bazata pe algoritmul KMP, o gasiti soon (admin?).
O solutie de 100 de puncte, bazata pe algoritmul Rabin-Karp, o gasiti soon (eu).