Pytania otagowane jako string-matching

1
Rabin – Karp vs Karp – Rabin
Mądrzy inni redaktorzy Wikipedii odrzucili moją prośbę o przeniesienie artykułu z Wikipedii na temat algorytmu Rabin – Karp do tego, co moim zdaniem powinno się nazywać, algorytm Karp – Rabin, ponieważ częściej używa się nazwy Rabin – Karp ( fałsz, jeśli ktoś idzie według liczb uczonego Google) lub że brzmi …

8
Obliczanie odległości Levenshteina szybko
Biorąc pod uwagę ogromną bazę dozwolonych słów (posortowane alfabetycznie) i słowo, znajdź słowo z bazy danych, która jest najbliższa podanemu słowu pod względem odległości Levenshteina. Naiwnym podejściem jest oczywiście po prostu obliczenie odległości levenshteina między danym słowem a wszystkimi słowami w słowniku (możemy przeprowadzić wyszukiwanie binarne w bazie danych przed …

2
n-wymiarowe dopasowanie wzoru
Jakie są znane wyniki znalezienia dokładnej n-wymiarowej podtablicy wewnątrz n-wymiarowej tablicy? W 1D jest to tylko problem dopasowania łańcucha, KMP robi to w czasie liniowym. W 2D ten dokument pokazał, że można to zrobić w czasie liniowym z niewielką dodatkową przestrzenią. Czy ten problem można rozwiązać w najgorszym przypadku liniowym …

2
Edytuj odległość za pomocą operacji przesuwania
Motywacja: Współautor redaguje manuskrypt i chciałbym zobaczyć jasne podsumowanie edycji. Wszystkie narzędzia podobne do „diff” są zwykle bezużyteczne, jeśli zarówno przenosisz tekst (np. Reorganizując strukturę), jak i edytujesz lokalnie. Czy to naprawdę takie trudne? Definicje: Chciałbym znaleźć minimalną odległość edycji, gdzie dozwolone operacje to: „tanie” operacje: dodaj / zmień / …

1
Zakrywający sznur palindromami
Biorąc pod uwagę ciąg , okładka palindromu jest sekwencją słów tak że i takie, że każdy jest palindromem.w=σ1σ2…σnw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_np1p2⋯pmp1p2⋯pmp_1p_2\cdots p_mpipip_ip1p2⋯pm=wp1p2⋯pm=wp_1p_2\cdots p_m = wpipip_i Jak trudno jest znaleźć minimalną wielkość palindromu? (wydaje się to wykonalne przez programowanie dynamiczne, ale nie jestem pewien, czy to działa). Czy problem staje się trudniejszy, jeśli podany …

1
Słowa Fibonacciego
W moim starym czeskim podręczniku algorytmów natknąłem się na następujący problem, niestety przyszedł bez wskazówek i rozwiązania. „Określamy Fibonacciego słów , , , gdzie i są ogólnie literami. Jak w danej ciąg (ponad potencjalnie dużym alfabetem) czy możesz znaleźć najdłuższe pod-słowo Fibonacciego w czasie liniowym? ”F 1 = b F …

2
Złożoność homogenizacji łańcucha
Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo naturalnego problemu, który wydaje się mieć połączenia do edycji odległości, grupowania przez zamianę i …

4
Czy drzewa sufiksów mogą być użyte do znalezienia wszystkich popularnych podciągów?
Próbuję użyć drzewa sufiksów do porównania sekwencji ciągów. Znalazłem implementacje / teorię najdłuższego wspólnego problemu podciągów przy użyciu drzewek sufiksów. Jednak to, czego szukam, to omówienie powiązanego problemu - „wszystkich typowych podciągów”. W szczególności mam problem, w którym muszę najpierw znaleźć najdłuższy wspólny podciąg, a następnie znaleźć następny najdłuższy wspólny …

3
Dopasowanie wzorca permutacji w ciągach
Luźno mówiąc, dopasowanie wzorców permutacji dotyczy następujących problemów: Biorąc pod uwagę permutacje w S n i w , przy , czy zawiera podsekwencję o długości której elementy są uporządkowane według ?ππ\piSnSnS_nS m m ≤ n π τ m σσσ\sigmaSmSmS_mm≤nm≤nm\leq nππ\pi ττ\taummmσσ\sigma Na przykład, jeśli i , to podsekwencja pasuje do …


1
Decyzja, czy ciąg znaków zastępczych jest całkowicie dopasowany do innego ciągu znaków zastępczych w zestawie
Oto problem, który dręczy mnie od dłuższego czasu. Powiedzmy, że łańcuch jest sekwencją 1 i 0, a łańcuch wieloznaczny to sekwencja 1, 0 i? S. Wszystkie ciągi znaków i symbole wieloznaczne mają tę samą długość. Są to standardowe symbole wieloznaczne UNIX; 10 ?? 1 pasuje do 10011, 10111 itd. - …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.