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

Poveste si cerinta...

Se dau doua siruri $A$ si $B$. Se cere gasirea tuturor aparitiilor sirului $A$ ca subsecventa a sirului $B$.

h2. Date de intrare

Fisierul de intrare $strmatch.in$ ...

Fisierul de intrare $strmatch.in$ contine 2 linii cu sirurile $A$, respectiv $B$.

h2. Date de iesire

In fisierul de iesire $strmatch.out$ ...

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. Sirurile sunt indexate de la $0$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* Lungimea sirurilor $A$ si $B$ se afla in intervalul $[1, 1048575]$

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

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

| ABA
CABBCABABAB
| 2
5 7

|
h3. Explicatie

...

Cele doua aparitii sunt:
 
* $CABBC{*ABA*}BAB$
* $CABBCAB{*ABA*}B$

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

 
h3. 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":automate-finite-si-kmp de pe infoarena sau cu ajutorul algoritmului Rabin-Karp prezentat "aici":http://en.wikipedia.org/wiki/Rabin-Karp.
 
O solutie de 100 de puncte, bazata pe algoritmul KMP, o gasiti *soon* (admin?).
O solutie de 100 de puncte, bazata pe algoritmul Rabin-Karp, o gasiti *soon* (eu).