Aktywne Wpisy
kitty-cat +10
Nie mogę spać. Budzę się w okolicy 1-2 ale idzie zasnąć, potem 3-4 i zaczyna się problem no i znowu przed 5 i już ciężko jest zasnąć.
I tak co noc #!$%@?. Jestem notorycznie zmęczona, wręcz wyczerpana. Mam dość. (╥﹏╥)
#zalesie #spanie #bezsennosc
I tak co noc #!$%@?. Jestem notorycznie zmęczona, wręcz wyczerpana. Mam dość. (╥﹏╥)
#zalesie #spanie #bezsennosc
Potifara +44
W tym momencie na miejscu Sylwestra Wardęgi miałbym jedno wielkie „ale" do „Boxdela". Michał po Pandora Gate mógł pójść na dno, jak to zrobił Marcin Dubiel. Nie poszedł, bo jedną z bardzo mocnych pomocnych dłoni wystawił mu właśnie „Druid". Zrobił to, mimo że zdawał sobie sprawę, jakie konsekwencje taka postawa poniesie. A przede wszystkim jaki będzie miała odbiór. Wypominał to sam „Nitro", z którym teraz włodarz FAME-u się trzyma.
Sergiusz w tamtym
Sergiusz w tamtym
#programowanie
https://pl.wikipedia.org/wiki/Skompresowane_drzewo_trie
@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.
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)
@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.
@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.
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
@cevilo: uuu nie zesraj się się czasem panie superinteligencie
@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?
@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)
Tzn, jestem takiego samego zdania, ale chciałem się upewnić. Pewnie zrobili błąd przy określaniu limitów czasowych dla zadania
Komentarz usunięty przez autora
@imarid: sorki to nie w tym temacie i nie do ciebie miało być ( ͡° ͜ʖ ͡°)