Teoretyczne informatyka string-matching

1

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 …

26 ho.history-overview string-matching

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 …

24 ds.algorithms reference-request string-matching string-search

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 …

20 ds.algorithms reference-request string-matching

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ń / …

13 ds.algorithms reference-request parameterized-complexity string-matching edit-distance

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 …

12 ds.algorithms dynamic-programming string-matching covering-problems

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 …

11 string-matching string-search

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 …

10 cc.complexity-theory ds.algorithms reference-request string-matching edit-distance

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 …

10 ds.algorithms string-matching

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 …

10 permutations string-matching

1

Dopasowywanie wzorów za pomocą nie obchodzi: wiele wzorów

2-stronicowy papier SODA Kalai zapewnia prosty i skuteczny algorytm dopasowywania wzorców bez obojętności (symbole wieloznaczne pasujące do jednej postaci). Zasadniczo jest to tak łatwe jak splot. Ale co się stanie, jeśli szukamy wielu wzorów z „nie obchodzi”? Czy nadal możemy jakoś rozwiązać to za pomocą np. Technik opartych na FFT?

9 ds.algorithms reference-request string-matching

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. - …

9 ds.algorithms ds.data-structures approximation-algorithms string-matching string-search

Pytania otagowane jako string-matching