Potrivire

[•savim]

Aici puteti discuta despre problema potrivire

[•ms-ninja]

se poate sa existe litere mari in sirul A?

[•andreii1]

Se poate sa nu existe solutie?

[•geniucos]

In exemplu raspunsul e pentru subsir dar in fisierul de iesire scrie subsecventa.b trebuie sa fie subsecventa sau subsir al sirului dat?

[•wefgef]

Se poate sa nu existe solutie?

+

[•geniucos]

Sper ca ati observat ca s-a blocat evaluatorul la aceasta problema.

[•SpiderMan]

S-a blocat de tot .

[•Florian]

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

[•wefgef]

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

Sa modificati enuntul.

[•MciprianM]

acceptam solutii barbare

Cat de barbare?

[•repp4radu]

* din sirul B poate fi inlocuita cu o subsecventa care apartine neaparat sirului B, sau poate apartine si sirului A?

[•visanr]

De ce nu mai apare rezultatul evaluarii la problema asta?
La celelalte vad ca apare borderoul de evaluare.

[•blasterz]

Cred ca mergea in O(n + m) cu Aho Corasik... Era mai interesant daca erau limitele mai mari

[•PlayLikeNeverB4]

Eu am facut KMP.

[•blasterz]

Un singur KMP ? sau vreo 30?

[•tzipleatud]

Eu am facut 30 KMP.

[•PlayLikeNeverB4]

Nu conteaza cate sunt, pana la urma tot O(N + M) iese.

[•blasterz]

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

[•wefgef]

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.

[•Cristy94]

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

[•PlayLikeNeverB4]

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

Ne incurcam in simboluri
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.

[•maritim]

Ne incurcam in simboluri
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).

[•blasterz]

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

[•blasterz]

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

[•freak93]

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.