Pytania o ciągi symboli, ich zestawy i ich właściwości, a także zastosowania.
Próbuję napisać moduł sprawdzania pisowni, który powinien działać z dość dużym słownikiem. Naprawdę chcę efektywnego sposobu indeksowania danych słownikowych za pomocą odległości Damerau-Levenshteina w celu ustalenia, które słowa są najbliższe błędnie napisanemu słowu. Szukam struktury danych,...
Powiedzieć, że 1 2 ... n i są dwa ciągi o tej samej długości. Anagramming dwóch ciągów bijective mapowania tak, że dla każdego .a1a2…ana1a2…ana_1a_2\ldots a_nb1b2…bnb1b2…bnb_1b_2\ldots b_np:[1…n]→[1…n]p:[1…n]→[1…n]p:[1\ldots n]\to[1\ldots n]ai=bp(i)ai=bp(i)a_i = b_{p(i)}iii Może być więcej niż...
Szukam struktury danych, która przechowuje zestaw ciągów znaków nad zestawem znaków , zdolną do wykonywania następujących operacji. Oznaczmy D ( S ) , jak w strukturze danych przechowującej zestaw łańcuchy S .ΣΣ\SigmaD(S)D(S)\mathcal{D}(S)SSS Add-Prefix-Setna : biorąc pod uwagę pewien zestaw T...
Nieformalne oświadczenie o problemie: Biorąc pod uwagę ciąg znaków, np. ACCABBABACCABBABACCABBAB , chcemy pokolorować niektóre litery na czerwono, a niektóre na niebiesko (a niektóre wcale), tak że czytanie tylko czerwonych liter od lewej do prawej daje taki sam wynik jak czytanie tylko niebieskie...
Szukam struktury danych, która obsługuje efektywne przybliżone wyszukiwanie kluczy (np. Odległość Levenshteina dla ciągów znaków), zwracając możliwie najbliższe dopasowanie dla klucza wejściowego. Najlepszą strukturą danych, jaką do tej pory znalazłem, są drzewa Burkhard-Keller , ale zastanawiałem...
Jestem ciekawy, jak można bardzo kompaktowo skompresować domenę dowolnej nazwy hosta IDN (zgodnie z definicją w RFC5890 ) i podejrzewam, że może to stać się ciekawym wyzwaniem. Host lub nazwa domeny Unicode (etykieta U) składa się z ciągu znaków Unicode, zwykle ograniczonego do jednego języka w...
Niech będzie skończonym zestawem znaków o ustalonym rozmiarze. Niech będzie ciągiem znaków nad . Mówimy, że niepusty substrat z jest powtórzeniem, jeśli dla jakiegoś ciągu .α Σ β αΣΣ\Sigmaαα\alphaΣΣ\Sigmaββ\betaαα\alphaγβ= γγβ=γγ\beta = \gamma \gammaγγ\gamma Teraz moje pytanie dotyczy tego,...
Niepokoi mnie kwestia asymptotycznego czasu działania algorytmu Ukkonena , być może najpopularniejszego algorytmu do konstruowania drzewek sufiksów w czasie liniowym (?). Oto cytat z książki „Algorytmy na strunach, drzewach i sekwencjach” Dana Gusfielda (sekcja 6.5.1): „... wszystkie algorytmy...
Pracowałem nad następującym problemem z tej książki . Pewien język przetwarzania ciągów oferuje prymitywną operację, która dzieli ciąg na dwie części. Ponieważ ta operacja polega na skopiowaniu oryginalnego ciągu, n zajmuje ciąg n jednostek czasu o długości n, niezależnie od lokalizacji cięcia....
Biorąc pod uwagę dwa ciągi, jak możesz sprawdzić, czy są one wzajemną permutacją za pomocą spacji O (1)? Modyfikowanie ciągów znaków nie jest w żaden sposób dozwolone. Uwaga: odstęp O (1) w stosunku do długości łańcucha ORAZ wielkości
Otrzymujemy tablicę ze wszystkimi .a[1…n]a[1…n]a[1 \ldots n]a[i]>0a[i]>0a[i]>0 Teraz musimy dowiedzieć się, ile różnych sum można uformować z jego podstron (gdzie podtablica to ciągły zakres tablicy, tj. dla niektórych , suma jest sumą wszystkich elementy podtablicy). Na przykład, jeśli , to...
Odległość edycji Levenshtein-Distance między listami jest dobrze zbadanym problemem. Ale nie mogę znaleźć wiele możliwych ulepszeń, jeśli wiadomo, że żaden element nie występuje więcej niż raz na każdej liście . Załóżmy również, że elementy są porównywalne / sortowalne (ale listy do porównania...
Pracuję nad algorytmami wyszukiwania ciągów, które obsługują wyszukiwanie wielu wzorców. Znalazłem dwa algorytmy, które wydają się najsilniejszymi kandydatami pod względem czasu działania, a mianowicie Aho-Corasick i Rabin-Karp . Nie udało mi się jednak znaleźć kompleksowego porównania między dwoma...
Podczas wywiadu na stanowisko programisty Java zapytano mnie: Napisz funkcję, która przyjmuje dwa parametry: ciąg znaków reprezentujący dokument tekstowy i liczba całkowita podająca liczbę elementów do zwrócenia. Zaimplementuj funkcję tak, aby zwracała listę ciągów uporządkowanych...
Ta strona o algorytmie Knuth-Moriss-Pratt w porównaniu do Boyera-Moore'a opisuje możliwy przypadek, w którym algorytm Boyera-Moore'a cierpi z powodu małej odległości pominięcia, podczas gdy KMP może działać lepiej. Szukam dobrego przykładu (tekst, wzór), który może jasno zademonstrować ten...
Szukam szybkiego algorytmu dopasowywania ciągów typu k-mismatch. Biorąc pod uwagę ciąg wzorca P o długości m i ciąg tekstowy T o długości n, potrzebuję szybkiego algorytmu (czas liniowy), aby znaleźć wszystkie pozycje, w których P pasuje do podłańcucha T z co najwyżej k niedopasowań. Różni się to...
Biorąc pod uwagę dwa symbole i b , niech określić k -tego ciąg Fibonacciego, co następuje:zaa\text{a}bb\text{b}kkk fa( k ) = ⎧⎩⎨bzafa( k - 1 ) ⋆ F.( k - 2 )jeśli k=0jeśli k=1jeszczeF(k)={bif k=0aif k=1F(k−1)⋆F(k−2)else F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1...
Szukam wydajnego algorytmu do znajdowania najdłuższego powtarzającego się wzorca w ciągu. Weźmy na przykład następujący ciąg liczb: 5431428571428571428571428571427623874534. Jak widać, 142857142857jest to najdłuższy wzór, który powtarza się kilka razy (przynajmniej dwa razy) w tym...
Załóżmy, że otrzymaliśmy zbiór ciągów, . Chciałbym wiedzieć, czy którykolwiek z tych ciągów jest podciągiem dowolnego innego ciągu w kolekcji. Innymi słowy, chciałbym algorytm dla następującego zadania:nnnS.1, ... ,S.nS1,…,SnS_1,\dots,S_n Dane wejściowe:S.1, ... ,S.nS1,…,SnS_1,\dots,S_n Wyjście:...
Biorąc pod uwagę ciąg sss, Chciałbym znaleźć najdłuższą powtarzającą się (przynajmniej dwukrotnie) podsekwencję. To znaczy, chciałbym znaleźć ciągwww który jest podciągiem (nie musi być ciągły) z sss takie, że w=w′⋅w′w=w′⋅w′w=w' \cdot w' . To jest,wwwto ciąg, którego połówki pojawiają się dwa razy...