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 wypisywać 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.
- Nie powinno być już podłańcucha A, który spełnia pierwszą właściwość.
Na przykład:
A = xxxappleyyyyyyy
B = zapplezzz
Podłańcuch apple
z indeksami 4 8
(indeksowanie od 1) byłby prawidłowym wyjściem.
Funkcjonalność
Możesz założyć, że dane wejściowe będą w standardzie w lub w pliku w katalogu lokalnym, który jest twoim wyborem. Format pliku to po prostu dwa ciągi znaków, oddzielone nowym wierszem. Odpowiedzią powinien być pełny program, a nie tylko funkcja.
W końcu chciałbym przetestować twój kod na dwóch podciągach pobranych z ciągów w http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ .
Wynik
To jest golf golfowy z niespodzianką. Twój kod musi być uruchamiany w O(n)
czasie, gdzie n
jest całkowitą długością danych wejściowych.
Języki i biblioteki
Możesz używać dowolnego języka, który ma swobodnie dostępny kompilator / tłumacz / etc. dla systemu Linux. Powinieneś używać tylko standardowych bibliotek open source nieprzeznaczonych do rozwiązania tego zadania. W przypadku sporu policzę to jako dowolną bibliotekę, która jest standardem w Twoim języku lub biblioteką, którą możesz zainstalować na domyślnej maszynie ubuntu z domyślnego repozytorium.
Przydatna informacja
Istnieją co najmniej dwa sposoby rozwiązania tego problemu w czasie liniowym. Jednym z nich jest najpierw obliczenie drzewa sufiksów, a drugim - najpierw obliczenie tablicy sufiksów i tablicy LCP.
- Oto pełne i (być może zbyt) szczegółowe wyjaśnienie budowy drzewa z liniowym sufiksem czasu (okazuje się, że niektóre liczby są niestety pomieszane). Na stronie https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-alameterm-in-plain-english znajduje się również bardzo ładna odpowiedź SO . Zawiera również link do kodu źródłowego. Inne szczegółowe wyjaśnienie można znaleźć tutaj , tym razem dając pełne rozwiązanie w C.
- Sekcja 2 http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf zawiera algorytm budowy macierzy sufiksu liniowego, a dodatek A zawiera kod źródłowy C ++. Ta odpowiedź pokazuje, jak obliczyć najdłuższy wspólny podciąg https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings-using-suffix-arrays . Sekcja 5 https://courses.csail.mit.edu/6.851/spring12/scribe/lec16.pdf, który ma również powiązany wykład wideo https://courses.csail.mit.edu/6.851/spring12/lectures/L16 .html wyjaśnia również ten sam algorytm od 1:16:00.
źródło
O(n) time
Jesteś pewien, że to możliwe?Odpowiedzi:
Python 2, 646 bajtów
Wykorzystuje to algorytm skosu opisany w „Prostej konstrukcji tablicy sufiksu pracy liniowej” Kärkkäinena i Sandersa. Implementacja C ++ zawarta w tym dokumencie wydaje się już trochę „golfowa”, ale wciąż jest dużo miejsca na jej skrócenie. Na przykład możemy powtarzać się, dopóki nie dojdziemy do tablicy o długości jeden, zamiast zwarcia jak w dokumencie, bez naruszenia
O(n)
wymogu.W części LCP śledziłem „Obliczenia najdłuższego wspólnego z prefiksem w czasie liniowym w tablicach sufiksów i jego zastosowaniach” autorstwa Kusai i in.
Program generuje wyjście,
1 0
jeśli najdłuższy wspólny podciąg jest pusty.Oto trochę kodu programistycznego, który zawiera wcześniejszą wersję programu, który jest nieco bliżej implementacji C ++, kilka wolniejszych podejść do porównania oraz prosty generator przypadków testowych:
źródło