Zadanie
Zadanie polega na golfie w wybrany przez siebie algorytm dokładnego dopasowywania ciągów w czasie rzeczywistym.
Wejście
Dwa wiersze tekstu dostarczane na standardowym wejściu, oddzielone nowym wierszem. Pierwszy wiersz zawiera „wzór” i będzie po prostu łańcuchem ASCII narysowanym z liter a-z
.
Drugi wiersz zawiera dłuższy „tekst” i będzie również po prostu łańcuchem ASCII narysowanym z liter a-z
.
Wynik
Lista wskaźników, w których występują dokładne dopasowania. Powinieneś podać pozycję początku każdego meczu, który ma miejsce.
Specyfikacja
Twój algorytm może spędzać czas liniowy na wstępnym przetwarzaniu wzorca. Następnie musi odczytać tekst od lewej do prawej i poświęcić stały czas każdemu znakowi w tekście i wypisać każde nowe dopasowanie, gdy tylko się pojawi. Mecze mogą się oczywiście nakładać na siebie.
Algorytm
Istnieje wiele algorytmów dopasowania ścisłego w czasie rzeczywistym. Jeden jest wspomniany na przykład na wiki dla KMP . Możesz użyć dowolnego, który Ci się podoba, ale zawsze musisz podać prawidłową odpowiedź.
Będę prowadzić tabelę liderów dla poszczególnych języków, aby ci, którzy preferują popularne języki, mogli wygrać na swój własny sposób. Wyjaśnij, który algorytm zaimplementowałeś.
Czas rzeczywisty
Wygląda na to, że doszło do zamieszania w kwestii tego, co oznacza czas rzeczywisty. Nie oznacza to po prostu czasu liniowego. Tak więc standardowy KMP nie działa w czasie rzeczywistym. Link w pytaniu wyraźnie wskazuje część strony wiki KMP na temat wariantu KMP w czasie rzeczywistym. Boyer-Moore-Galil również nie jest w czasie rzeczywistym. To pytanie / odpowiedź na ten temat omawia problem lub można po prostu wyszukać w Google „dokładne dopasowanie w czasie rzeczywistym” lub podobne warunki.
źródło
abcd
iacbdefg
wyprowadziłbym1 4
, dlaa
id
?a
id
pasują do siebie. Istniejeabcd
iacbdefg
,a
id
są w identycznych pozycjach.Odpowiedzi:
Python 2, 495 bajtów
Jest to KMP w czasie rzeczywistym, który jest znacznie krótszy i tylko nieco wolniejszy niż algorytm BMG (który jest zwykle sublinearny). Zadzwoń z
K(pattern, text)
; wynik jest identyczny z algorytmem BMG.źródło
Python 2, 937 bajtów
To wcale nie jest krótkie, ale (a) działa, (b) spełnia wszystkie wymagania, i (c) gra w golfa tak bardzo, jak tylko mogę.
Jest to implementacja algorytmu Boyera-Moore-Galila. Całkiem proste - zadzwoń z
S(pattern,text)
; pozostałe dwie funkcje są używane w procesie wstępnego przetwarzania. Rzeczywiście, wszystko oprócz ostatnich 5 linii jest przetwarzaniem wstępnym.Przykładowy przebieg, który zajął około sekundy:
źródło
O(m)
wstępnego przetwarzania iO(n)
dopasowywania [=>O(n+m)
], co robi (lub lepiej).O(n+m)
czasie, ale na przykład jeden z symboli w tekście może zająć n czasu.KMP, Python 2 (213 bajtów)
Wersja bez golfa. Pierwszą pętlą jest zbudowanie automatów KMP. Druga pętla chodzi po automatach. Dzielą one prawie ten sam wzór, ale ich wyodrębnienie będzie kosztować więcej bajtów, więc dla golfa kodowego wolę powielić tę logikę. Podobne wdrożenie jest faktycznie szeroko stosowane w programowaniu konkursów.
źródło
Realtime KMP, Python 2 (167 bajtów)
W normalnym KMP symulujemy zachowanie automatu za pomocą funkcji fail. W tym KMP w czasie rzeczywistym konstruowany jest pełny automat, aby w dopasowanym wyrażeniu mógł przetwarzać każdy znak w czasie rzeczywistym (stały czas).
Złożoność czasu i złożoności przetwarzania wstępnego wynosi O (nm), gdzie m jest rozmiarem alfabetu, a n jest długością łańcucha wzorca. Jednak w moich testach rzeczywisty rozmiar tabeli przejścia jest zawsze mniejszy niż 2n, więc może możemy udowodnić, że złożoność czasu i przestrzeni wynosi O (n).
Wersja bez golfa
źródło
Q, 146 bajtów
Test
generuje 15 i 34
Notatki
Nie ogranicza się do alfabetu (obsługuje dowolny znak ascii i rozróżnia małe i wielkie litery).
Nie używa żadnej konkretnej operacji zdefiniowanej przez Q na ciągach -> działa na ciągach jako sekwencjach (dopasowanie operacji, długość itp.)
Minimalizuje tabelę przejściową łączącą wszystkie znaki nie będące wzorami jako jedna unikalna klasa znaków.
Potrafię trochę wycisnąć kod. To pierwsza próba weryfikacji strategii rozwiązania
Odwiedź dowolną postać tekstu dokładnie raz, a dla każdego wprowadzanego znaku jest unikalny skok. Zakładam więc, że wyszukiwanie pasuje do „czasu rzeczywistego”
Konstrukcja tabeli al stan i i char c szukają najdłuższego podłańcucha, który kończy się na i, a po dołączeniu c jest prefiksem S. Konstrukcja nie jest zoptymalizowana, więc nie wiem, czy jest poprawna
Format wejściowy nie pasuje dobrze do języka. Przekazanie dwóch argumentów ciągu spowoduje zapisanie 16 bajtów
Wyjaśnienie
globalny W reprezentuje wzorzec, a S odpowiada tekstowi do wyszukiwania
x:1_"\n "\:x
dziwny kod, aby poradzić sobie z wymaganiami wejściowymi (Q wymaga, aby łańcuchy wielowierszowe zawierały wcięcia nie pierwsze, więc musi odrzucić dodatkowe miejsce przed każdym nie pierwszym wierszem)n::#W
oblicza długość W i zapisuje jako globalną nu::?W
oblicza unikalne znaki w W i zapisuje jako globalny uu?S
generuje klasę characted dla każdego znaku SZbuduj tabelę przejściową T z jednym rzędem na unikalny znak w W (plus jeden dodatkowy) i kolumną dla każdego indeksu w W (plus jeden dodatkowy). Dodatkowy wiersz odpowiada stanowi początkowemu, a dodatkowa kolumna zbiera dowolny znak w S, ale nie w W. Ta strategia minimalizuje rozmiar tabeli
p:{$[n<#x;0;x~(#x)#W;#x;0]}
to funkcja wyszukująca najdłuższy prefiksf:{{|/p'x}'((1_)\x#W),\:/:u}
jest funkcją, która oblicza rząd x TWyszukaj tekst za pomocą tabeli przejścia.
T\[0;u?S]
iteruje ponad 0 (stan początkowy) i każdą klasę znaków S, używając jako nowej wartości wartości z tabeli przejścia T [stan] [charClass]. Stany końcowe mają wartość n, więc szukamy tej wartości w sekwencji stanów i zwracamy ją skorygowaną (aby wskazać początkową zamiast końcową pozycję każdego dopasowania)źródło
Boyer-Moore, Perl (50)
Perl próbuje użyć Boyer-Moore w naturalny sposób:
źródło