| 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 (0 ≤ i < |B|), dacă i + |A| ≤ |B| şi există cel mult K poziţii j (0 ≤ j < |A|), pentru care A[j] != B[i + j].
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
- Cele două şiruri conţin doar caractere din alfabetul latin.
- Numerotarea caracterelor începe cu poziţia 0.
Exemplu
| partialmatch.in | partialmatch.out |
|---|---|
| abba abbaaba 1 | 2 0 3 |
| baa ccba 1 | 0 |
Explicaţie
Există două aproape-potriviri ale lui A peste B:
abbaaba
abba
abbaaba
abba
