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

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

h3. Indicatii de rezolvare

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.

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

Desi atat $KMP$ cat si $Rabin-Karp$ au complexitate liniara, in practica, $KMP$ este mai rapid.
 
h3. Probleme asemanatoare
 
* Infoarena - "Prefix":problema/prefix
* Infoarena - "Reguli":problema/reguli