Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | partialmatch.in, partialmatch.out | Sursă | Infoarena Monthly 2014, Runda 7 |
| Autor | Costin Oncescu | Adăugată de |  Cristian Lambru •maritim |
| Timp execuţie pe test | 0.95 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Partial Match
Pentru că Antonio şi Antonia sunt plecaţi la mare, vă prezentăm un alt tip de problemă, cu un enunţ super scurt:
Se dau două şiruri de caractere A şi B şi un număr natural K. Se cere să se spună pe câte poziţii şirul A se "aproape-potriveşte" peste şirul B.
Un şir A se "aproape-potriveşte" peste un alt şir B pe o poziţie i, dacă i + |B| - 1 <= |A| şi există cel mult K poziţii j (1 ≤ j ≤ |B|), pentru care A[j] != B[i + j - 1].
Date de intrare
Fişierul de intrare partialmatch.in conţine pe prima linie şirul A, pe a doua linie şirul B, iar pe a treia linie numărul K.
Date de ieşire
În fişierul de ieşire partialmatch.out veţi afişa numărul aproape-potrivirilor lui A peste B şi poziţiile acestora, câte un număr pe linie.
Restricţii
- 1 ≤ |A|, |B| ≤ 100.000
- 0 ≤ K ≤ 10
Exemplu
| partialmatch.in | partialmatch.out |
|---|---|
| abba abbaaba 1 | 2 0 3 |
Explicaţie
Există două aproape-potriviri ale lui A peste B:
abbaaba
abba
abbaaba
abba
