strmatch

Potrivirea sirurilor

h2. Date de iesire

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

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, 1048575]$

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

h2. Exemplu

* $CABBC{*ABA*}BAB$
* $CABBCAB{*ABA*}B$

== include(page="template/taskfooter" task_id="strmatch") ==
 
h3. Indicatii de rezolvare

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 *soon* (admin?).
O solutie de 100 de puncte, bazata pe algoritmul Rabin-Karp, o gasiti *soon* (eu).

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") ==
 
 
 

2763