Fişierul intrare/ieşire:strmatch.in, strmatch.outSursăad-hoc
AutorArhiva EducationalaAdăugată deDenisONIcBanu Denis Andrei DenisONIc
Timp execuţie pe test0.3 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

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.instrmatch.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content