[imarid]

Da się znaleźć wszystkie możliwe substringi danego Stringa w czasie O(n)? Na rekrutacje miałem coś takiego i wała mi nie pasuje, żeby to można było zrobić w mniej jak O(n^2) ( ͡° ʖ̯ ͡°)
#programowanie

[cevilo]

@imarid: Da się, w tak sformułowanym problemie nie ma nic, ile czasu możesz poświęcić na budowę struktury danych. Zakładasz, że ten czas na budowę to O(1), czyli na wejściu słowo, ale jeśli poświęci się trochę więcej czasu, np. O(n) to i wyszukiwanie/wypisywanie staje się szybsze:
https://pl.wikipedia.org/wiki/Skompresowane_drzewo_trie

[pkh]

@imarid:: Strasznie glupie zadanie na rekrutacje - mozna zrobic suffix tree i to zajmuje O(n). To jest reprezentacja wszystkch substringow, tyle ze wypisanie tego zajmie O(n^2)

[leoha]

Zakładasz, że ten czas na budowę to O(1)

@cevilo: błąd... nie możesz tego założyć, jeśli czas budowania struktury będzie zależał od długości stringa lub substringa.

[imarid]

@pkh: @cevilo: z tym, że zadanko miałem, że dla każdego możliwego podciągu znaków danego ciągu znaków,
obliczyć ile jest unikalnych znaków,
i zsumować każdą taką wartość unikatowych znaków dla każdego, i to wszystko w czasie O(n) niby miało być i limit pamięci też O(n)

[cevilo]

@leoha: Nie zrozumiałeś w ogóle o czym napisałem, przeczytaj to spokojnie jeszcze raz.

[leoha]

Strasznie glupie zadanie na rekrutacje

@pkh: dlaczego? Wg mnie jest właśnie ok, bo sprawdza jak będziesz sobie radził z rowiązywaniem problemów, czy potrafisz konstruować algorytmy czy wiesz co to złożoność itd.

[leoha]

Nie zrozumiałeś w ogóle o czym napisałem, przeczytaj to spokojnie jeszcze raz.

@cevilo: Przeczytałem dokładnie i dokładnie zrozumiałem o co chodzi. W zadaniu widać, że masz dany string i substring i masz znależć ilość wystąpień, więc nie możesz ot tak sobie pominąć czegoś co dla ciebie niewygodne.

[cevilo]

@leoha: z reguły z mało inteligentnymi ludźmi nie dyskutuję, ale zrobię wyjątek.
Autor szukał rozwiązania przy założeniu budowy wejścia w czasie O(1), czyli ma podane słowo, string i już musi przystąpić do wyszukiwania substringów, daltego przychodziły mu do głowy jedynie rozwiązania O(n2)
Z tak sformułowanego problemu wcale nie wynika, że nie może najpierw poświęcić więcej czasu na obróbkę danych na wejściu, np na zbudowanie odpowiedniego drzewa w czasie O(n), wówczas wypisze

[leoha]

z reguły z mało inteligentnymi ludźmi nie dyskutuję, ale zrobię wyjątek.

@cevilo: uuu nie zesraj się się czasem panie superinteligencie

[leoha]

Da się znaleźć wszystkie możliwe substringi danego Stringa w czasie O(n)?

@imarid: mógłbyś doprecyzować czy chodzi o znalezienie wszystkich wystąpień danego substringa w stringu czy o znalezienie wszystkich możliwych substringów w stringu?

[cevilo]

@leoha: podziękuj za lekcję i nie pyskuj

[imarid]

@leoha: dla każdego możliwego substringu danego stringu trzeba było obliczyć ile jest unikalnych znaków, i wszystko to zssumować. Dla dużych ciągów mega duże liczby wychodziły. Maksymalna długość stringa to chyba miliard znaków było albo 100mld

[leoha]

Da się znaleźć wszystkie możliwe substringi danego Stringa w czasie O(n)? Na rekrutacje miałem coś takiego i wała mi nie pasuje, żeby to można było zrobić w mniej jak O(n^2) ( ͡° ʖ̯ ͡°)

@imarid: jeśli chcesz znaleźć wszystkie substringi stringa (a nie wszystkie wystąpienia danego substringa w stringu) to sama ich liczba rośnie kwadratowo z długością stringa, wiec nie da się ich znaleźć w czasie O(n)

[imarid]

@leoha: Dla stringu "ACAX" suma wychodziła 16, bo A,C,A,X,AC,CA,AX,ACA,CAX itp i dla każdego takie substringu liczyłeś ile unikalnych znaków w nim jest, i łączną sumę z wszystkich takich substringów.
Tzn, jestem takiego samego zdania, ale chciałem się upewnić. Pewnie zrobili błąd przy określaniu limitów czasowych dla zadania

[kater]

@imarid: pytanie nie związane z zadaniem, możesz podać szczegóły dotyczące stanowiska?

[imarid]

@kater: programista java, test był z Codility xd

[imarid]

@leoha: co niby przekręcił? Za correctness miałem 100% za to zadanie, nie mogłem niczego przekręcić, za performance miałem 0% ( ͡° ʖ̯ ͡°)

[leoha]

co niby przekręcił? Za correctness miałem 100% za to zadanie, nie mogłem niczego przekręcić, za performance miałem 0% ( ͡° ʖ̯ ͡°)

@imarid: sorki to nie w tym temacie i nie do ciebie miało być ( ͡° ͜ʖ ͡°)

[leoha]

@imarid: czekaj czekaj... co dokładnie miało być wyjściem? liczba substringów, substringi, liczba unikalnych znaków czy jak? Jeśli to codility to nie sądzę, żeby tam był błąd... wklej swój kod, może masz coś innego jeszcze źle (np. używasz do kolektowania substringów jakiejś struktury co robi ci w sumie O(n^3).