To wyzwanie dotyczy pisania kodu w celu rozwiązania następującego problemu.
Biorąc pod uwagę dwa ciągi A i B, kod powinien wyświetlać indeksy początkowe i końcowe podłańcucha A o następujących właściwościach.
- Podciąg A powinien również pasować do niektórych podciągów B z maksymalnie jednym podstawieniem pojedynczego znaku w ciągu.
- Nie powinno być już podłańcucha A, który spełnia pierwszą właściwość.
Na przykład:
A = xxxappleyyyyyyy
B = zapllezzz
Podciąg apple
z indeksami4 8
(indeksowanie od 1) byłby prawidłowym wyjściem.
Wynik
Wynik twojej odpowiedzi będzie sumą długości twojego kodu w bajtach + czas w sekundach, jaki zajmuje mój komputer, gdy działa na ciągach A i B o długości 1 miliona każdy.
Testowanie i wprowadzanie
Uruchomię twój kod na dwóch ciągach o długości 1 miliona pobranych z ciągów w http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/
Dane wejściowe będą w standardzie i będą po prostu dwoma ciągami znaków, oddzielonymi nową linią.
Języki i biblioteki
Możesz używać dowolnego języka, który ma swobodnie dostępny kompilator / tłumacz / etc. dla Linuksa i wszelkich bibliotek, które są również open source i swobodnie dostępne dla Linuksa.
Moja maszyna Czasy zostaną uruchomione na moim komputerze. Jest to standardowa instalacja ubuntu na ośmiordzeniowym procesorze AMD FX-8350. Oznacza to również, że muszę być w stanie uruchomić Twój kod. W związku z tym używaj tylko łatwo dostępnego bezpłatnego oprogramowania i dołącz pełne instrukcje, jak skompilować i uruchomić kod.
źródło
if(hash(str1 == test1 && str2 == test2)) print("100,150") else ..
-- myśli?appley
potrzebuje dwóch podstawień w celu dopasowaniaapllez
. Może przegapiłeś, że jestapll
w B, a nieappl
?Odpowiedzi:
Czas C ++: O (n ^ 2), dodatkowa spacja: O (1)
Uzupełnienie danych 15K na moim komputerze zajmuje 0,2 s.
Aby go skompilować, użyj:
Aby go uruchomić, użyj:
Wyjaśnienie
Pomysł jest prosty, na ciąg
s1
is2
staramy się zrównoważyćs2
poprzezi
:Gdy przesunięcie wynosi 3:
Następnie dla każdego przesunięcia
i
wykonujemy dynamiczne skanowanie programujące nas1[i:]
is2
. Dla każdegoj
niechf[j, 0]
będzie maksymalna długośćd
taka, żes1[j - d:j] == s2[j - i - d: j - i]
. Podobnie, niechf[j, 1]
będzie maksymalną długościąd
taką, że łańcuchys1[j - d:j]
is2[j - i - d:j - i]
różni się co najwyżej 1 znaku.Dlatego
s1[j] == s2[j - i]
mamy:Inaczej:
I:
Ponieważ potrzebujemy tylko f [j - 1,:] do obliczenia f [j,:], tylko O (1) jest używane dodatkowe miejsce.
Wreszcie maksymalna długość będzie wynosić:
Kod
źródło
C ++
Próbowałem wymyślić dobry algorytm, aby to zrobić, ale dzisiaj jestem trochę rozproszony i nie mogłem wymyślić niczego, co by działało dobrze. Działa to w czasie O (n ^ 3), więc jest bardzo powolne. Inna opcja, o której myślałem, mogłaby być teoretycznie szybsza, ale zajęłaby przestrzeń O (n ^ 2), a przy wejściach 1M byłaby nawet gorsza.
To wstydliwe, przy wejściach 15 KB potrzeba 190 sekund. Spróbuję to poprawić. Edycja: Dodano przetwarzanie wieloprocesowe. Teraz potrzeba 37 sekund na wejście 15K w 8 wątkach.
źródło
i < a.length()
nai < a.length - (longestA.second - longestA.first)
(to samo dla j i b.length ()), ponieważ nie będziesz musiał przetwarzać żadnych dopasowań mniejszych niż twój najdłuższyR
Wydaje mi się, że komplikowałem problem z poprzednim rozwiązaniem. Jest to około 50% szybsze (23 sekundy na 15k strunach) niż poprzednie i dość proste.
Ze względu na język nigdy nie będzie to pretendent, ale bawiłem się trochę.
Nie jestem pewien jego złożoności, ale w ciągu kilku ~ 15 000 ciągów zajmuje 43 sekundy przy użyciu jednego wątku. Największą część tego stanowiło sortowanie tablic. Próbowałem kilka innych bibliotek, ale bez znaczącej poprawy.
Metoda:
źródło