191 Substr

[ditzone]

Aici puteţi discuta despre problema Substr.

[•rmikeweb]

Imi poate spune si mie cum se fac sufix array-urile in N log N. Nu stiu cum fac sortarea aia in O(n) implementat cu merge sort are complexitate N log^2N si iau 80p dar is curios cum se face  in N log N.

[•svalentin]

Radix sort? Bucket sort?

[•Marius]

Merge si countsort ?

[•wefgef]

probabil ca te referi la radix sort (trebuie sa sortezi dupa 2 chestii , de aia e radix).

[•Marius]

Da, e un hibrid intre countsort si radixsort.

Am citit in revista GInfo un articol despre Siruri de Sufixe si nu imi dau seama cum cu o sortare in O(N log N) complexitatea totala e O(N^2 log N). Scrie in mai multe locuri, dar presupun ca e o greseala. Corect este O(N log^2 N), nu ? (Pentru cei care au citit numarul 15/7 Noiembrie 2005)

[•bogdan2412]

Sortarea prezentata in acel articol este N log^2 N.. A fost data o errata la acel articol in urmatorul numar...

[•ssergiuss]

Exista vreun caz particular la testul 10? Chiar nu-mi dau seama ce este gresit la sursa mea si totusi pic testul 10. Daca ma poate ajuta cineva ii sunt recunoscator  .
L.E.
Testul 10 are sirul de caractere pe a doua linie?
Facand citirea:

Cod:

fin >> N >> K;
fin.ignore( 1, '\n' );
fin.getline( A, Dim );

iau 90p.
Facand citirea:

Cod:

fin >> N >> K;
fin.ignore( 10, '\n' );
fin.getline( A, Dim );

iau 100p.

[•narcis_vs]

Este vreo cineva care a luat 100 cu hash-uri?

[•mouse_wireless]

Este vreo cineva care a luat 100 cu hash-uri?

Am luat eu (raspuns cu 4 ani intarziere )