== include(page="template/taskheader" task_id="strmatch") ==
Poveste si cerinta...
Se dau doua siruri $A$ si $B$ formate din litere mici si mari ale alfabetului englez si din cifre. 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. Pentru a evita fisierele de output foarte mari, in cazul in care $N$ este mai mare decat $1000$ se vor afisa doar *primele $1000$* de pozitii. Sirurile sunt indexate de la $0$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* Lungimea sirurilor $A$ si $B$ se afla in intervalul $[1, 2 000 000]$
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$
h2. 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 "aici":job_detail/143570?action=view-source.
O solutie de 100 de puncte, bazata pe algoritmul Rabin-Karp, o gasiti "aici":job_detail/143514?action=view-source.
Desi atat $KMP$ cat si $Rabin-Karp$ au complexitate liniara, in practica, $KMP$ este mai rapid.
h2. Probleme asemanatoare
* Infoarena - "Prefix":problema/prefix
* Infoarena - "Reguli":problema/reguli
* PKU - "Milking grid":http://acm.pku.edu.cn/JudgeOnline/problem?id=2185
* PKU - "Cow patterns":http://acm.pku.edu.cn/JudgeOnline/problem?id=3167
== include(page="template/taskfooter" task_id="strmatch") ==
