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
@imarid: napisz co miało być wyjściem? suma długości wszystkich substringów? czy wszystkie substringi? Czy jeszcze coś innego. Z przykłady nie wynika wprost co miało być wyjściem
@imarid: ok... wprowadziłeś nas wszystkich w błąd tym pytaniem. Oczywiście da się zrobić w czasie lepszym niż O(n^2), ale trzeba użyć trochę matematyki i logiki. Jak wróce z pracy to ci pokaże.
@leoha: @imarid: A jesteś pewien, że algorytm ma być szybszy niż O(n^2)? Java, operacje na stringach - jest możliwe, że miałeś bardzo niewydajną implementację która np. przypadkowo tworzyła masę tymczasowych stringów?
@cevilo: Pytanie zadanie przez op jest zle napisane albo bylo zle zadane. Tak jak napisales mozna skonsrulowac drzewo ktore w O(n) bedzie przechowywalo wszystkie stringi, ale to nie znaczy ze je 'znalazles'. Trzeba jeszcze je z tego drzewa wyciagnac (bo sa trzymane w specyficznej formie). A wypisanie to juz O(n^2) - i to rzuca na zlozonosc problemu. Nie wypisac n^2 stringow w czasie n jak piszesz ;D
@leoha to może ktoś w końcu #!$%@? napisać CO ma być tym rozwiązaniem jak nie substringi? Już 20 razy to napisaliście OKEJ ROZUMIEM więc może ktoś wklei aktualne zadanie bo jak was czytam to #!$%@? wiem o co chodzi a też bym chciał znać rozwiązanie. @imarid
@Dzolejro: Przykładowe wejście "ACAX". Liczysz dla każdego substringu unikalną ilość znaków. A 1 AC 2 ACA 1 ACAX 2 C 1 CA 2 CAX 3 A 1 AX 2 X 1 ---------------- SUMA=16 16 jest wynikiem
@leoha: @imarid: Noo jakby rozwiązaniem była długość wszystkich substringów, to problem byłby trywialny :P Wydawało mi się, że mam coś O(n logn) ale problematyczne jest przechowywanie i sprawdzanie unikalnej liczby znaków w każdym podciągu.
#programowanie
https://www.wykop.pl/wpis/29581833/da-sie-znalezc-wszystkie-mozliwe-substringi-danego/#comment-105049859
@imarid: napisz co miało być wyjściem? suma długości wszystkich substringów? czy wszystkie substringi? Czy jeszcze coś innego. Z przykłady nie wynika wprost co miało być wyjściem
@imarid: ok... wprowadziłeś nas wszystkich w błąd tym pytaniem. Oczywiście da się zrobić w czasie lepszym niż O(n^2), ale trzeba użyć trochę matematyki i logiki.
Jak wróce z pracy to ci pokaże.
@wolodia: Tak ma być szybszy, ale wyjściem nie mają być substringi jak sugeruje OP w pytaniu.
@leoha: Ten problem
@imarid: ale na pisałeś też:
:p
@imarid
Przykładowe wejście "ACAX". Liczysz dla każdego substringu unikalną ilość znaków.
A 1
AC 2
ACA 1
ACAX 2
C 1
CA 2
CAX 3
A 1
AX 2
X 1
----------------
SUMA=16
16 jest wynikiem
Nie wiem czy już prościej mogę to rozpisać.
@imarid: tu powinno być 2 i 3, nie?
@leoha: @imarid: Noo jakby rozwiązaniem była długość wszystkich substringów, to problem byłby trywialny :P Wydawało mi się, że mam coś O(n logn) ale problematyczne jest przechowywanie i sprawdzanie unikalnej liczby znaków w każdym podciągu.