Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: Potrivire  (Citit de 9796 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
savim
Nu mai tace
*****

Karma: 194
Deconectat Deconectat

Mesaje: 333



Vezi Profilul
« : Mai 11, 2012, 14:06:05 »

Aici puteti discuta despre problema potrivire
Memorat
ms-ninja
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #1 : Mai 11, 2012, 15:16:40 »

se poate sa existe litere mari in sirul A?
Memorat
andreii1
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 23



Vezi Profilul
« Răspunde #2 : Mai 11, 2012, 15:32:42 »

Se poate sa nu existe solutie?
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #3 : Mai 11, 2012, 15:34:16 »

In exemplu raspunsul e pentru subsir dar in fisierul de iesire scrie subsecventa.b trebuie sa fie subsecventa sau subsir al sirului dat?
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #4 : Mai 11, 2012, 15:55:38 »

Se poate sa nu existe solutie?

+
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #5 : Mai 11, 2012, 15:56:10 »

Sper ca ati observat ca s-a blocat evaluatorul la aceasta problema.
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #6 : Mai 11, 2012, 15:59:19 »

S-a blocat de tot Tongue.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #7 : Mai 11, 2012, 16:11:51 »

In cazul in care nu exista solutie, se afiseaza -1.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #8 : Mai 11, 2012, 16:12:13 »

In cazul in care nu exista solutie, se afiseaza -1.

Sa modificati enuntul.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #9 : Mai 11, 2012, 17:03:17 »

Citat
acceptam solutii barbare

Cat de barbare?
Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #10 : Mai 11, 2012, 17:43:07 »

* din sirul B poate fi inlocuita cu o subsecventa care apartine neaparat sirului B, sau poate apartine si sirului A?
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #11 : Mai 11, 2012, 19:23:02 »

De ce nu mai apare rezultatul evaluarii la problema asta?
La celelalte vad ca apare borderoul de evaluare.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #12 : Mai 11, 2012, 22:08:26 »

Cred ca mergea in O(n + m) cu Aho Corasik... Era mai interesant daca erau limitele mai mari Smile
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #13 : Mai 11, 2012, 22:19:52 »

Eu am facut KMP.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #14 : Mai 11, 2012, 22:23:12 »

Un singur KMP ? sau vreo 30?
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #15 : Mai 11, 2012, 22:32:04 »

Eu am facut 30 KMP.
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #16 : Mai 11, 2012, 22:36:16 »

Nu conteaza cate sunt, pana la urma tot O(N + M) iese.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #17 : Mai 11, 2012, 22:52:30 »

Esti sigur?  Eu cred ca iese O(30 * O(n + m)),
iar 30 nu e constanta... e numarul de *
« Ultima modificare: Mai 11, 2012, 22:58:31 de către Mircea Dima » Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #18 : Mai 11, 2012, 22:59:47 »

Esti sigur?  Eu cred ca iese O(30 * O(n + m)),
iar 30 nu e constanta... e numarul de *

Merge in O(N + M) cu KMP indiferent de numarul de stelute.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #19 : Mai 11, 2012, 23:13:03 »

Merge si brut, fara niciun fel de optimizare (chiar mai repede decat KMP din ce am vazut)
http://infoarena.ro/job_detail/747839
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #20 : Mai 11, 2012, 23:19:05 »

Esti sigur?  Eu cred ca iese O(30 * O(n + m)),
iar 30 nu e constanta... e numarul de *
Ne incurcam in simboluri Very Happy
Cele 30 de KMP-uri nu se fac pe toata lungimea sirului, ci doar pe portiunile dintre stelute. De aceea, per total, e ca si cum ai face o singura data pe tot sirul.
Memorat
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #21 : Mai 11, 2012, 23:56:09 »

Ne incurcam in simboluri Very Happy
Cele 30 de KMP-uri nu se fac pe toata lungimea sirului, ci doar pe portiunile dintre stelute. De aceea, per total, e ca si cum ai face o singura data pe tot sirul.

Nu exact. Intradevar, pana la urma M-ul, in cazul nostru lungimea fiecarei secvente delimitate de doua stelute este in total lungimea lui B, dar KMP-ul se repeta de fiecare data cand se gaseste o noua astfel de secventa . La dimensiuni imense ale sirului si la un numar mai mare de stelute, complexitatea O(nr_stelute * (M + N)) este diferita in practica fata de O(M+N).
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #22 : Mai 11, 2012, 23:57:08 »

Atunci eu faceam KMP de 30 de ori... calculam prefixul pt fiecare portiune dintre stelute si apoi mergeam de 30 de ori pe primul sir.
Deci la mine chiar e O(30 * (N + M)). Daca voi faceti altfel...
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #23 : Mai 11, 2012, 23:59:32 »

Esti sigur?  Eu cred ca iese O(30 * O(n + m)),
iar 30 nu e constanta... e numarul de *

Merge in O(N + M) cu KMP indiferent de numarul de stelute.


Wef, tu ai bagat un singur KMP ? sigur ai O(N + M) ? Eu cred ca O(N + M) merge doar cand bagi Aho Corasik
peste sirurile dintre stelute...
Memorat
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 342
Deconectat Deconectat

Mesaje: 819



Vezi Profilul
« Răspunde #24 : Mai 12, 2012, 02:18:18 »

Merge si un singur KMP in care consideri ca * se potriveste cu orice. La functia prefix(si implicit si la KMP) te intorci pana la ultima steluta potrivita cand nu e bun caracterul curent.
Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines