Diferente pentru problema/strmatch intre reviziile #7 si #15

Nu exista diferente intre titluri.

Diferente intre continut:

* $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.
Desi atat $KMP$ cat si $Rabin-Karp$ au complexitate liniara, in practica, $KMP$ este mai rapid.
h3. Probleme asemanatoare
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") ==
 
 
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
2763