| 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 formate din litere mici si mari ale alfabetului englez si din cifre. 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. Pentru a evita fisierele de output foarte mari, in cazul in care N este mai mare decat 1000 se vor afisa doar primele 1000 de pozitii. Sirurile sunt indexate de la 0.
Restrictii
- Lungimea sirurilor A si B se afla in intervalul [1, 2 000 000]
Exemplu
| strmatch.in | strmatch.out |
|---|---|
| ABA CABBCABABAB | 2 5 7 |
Explicatie
Cele doua aparitii sunt:
- CABBCABABAB
- CABBCABABAB
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 aici.
O solutie de 100 de puncte, bazata pe algoritmul Rabin-Karp, o gasiti aici.
Desi atat KMP cat si Rabin-Karp au complexitate liniara, in practica, KMP este mai rapid.
Probleme asemanatoare
- Infoarena - Prefix
- Infoarena - Reguli
- PKU - Milking grid
- PKU - Cow patterns
