Potrivirea sirurilor

strmatch

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

h2. Indicatii de rezolvare

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

Desi atat $KMP$ cat si $Rabin-Karp$ au complexitate liniara, in practica, $KMP$ este mai rapid.

h2. Probleme asemanatoare

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