Fişierul intrare/ieşire:partialmatch.in, partialmatch.outSursăInfoarena Monthly 2014, Runda 7
AutorCostin OncescuAdăugată demaritimCristian Lambru maritim
Timp execuţie pe test1.9 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inpartialmatch.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content