partialmatch

Partial Match

== include(page="template/taskheader" task_id="partialmatch") ==

Poveste şi cerinţă...

_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 &le; i < |B|)$, dacă $i + |A| &le; |B|$ şi există cel mult $K$ poziţii $j (0 &le; j < |A|)$, pentru care $A[j] != B[i + j]$.

h2. Date de intrare

Fişierul de intrare $partialmatch.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $partialmatch.out$ ...

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

h2. 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.$

h2. Exemplu
table(example). |_. partialmatch.in |_. partialmatch.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| abba
abbaaba
1
| 2
0
3
|
| baa
ccba
1
| 0
|

h3. Explicaţie

...

Există două aproape-potriviri ale lui $A$ peste $B$:
 
${+abba+}aba$
${+abba+}$
 
$abb{+a+}a{+ba+}$
$   {+a+}b{+ba+}$

== include(page="template/taskfooter" task_id="partialmatch") ==

10110