Exact Covers and Pattern Matching with Mismatches

Praca jest kompilacją serii wyników z dziedziny algorytmów tekstowych. W szczególności rozważamy warianty problemu znajdowania szablonu i wyszukiwania wzorca w tekście z niedopasowaniami. Jako n będziemy oznaczać długość wejściowego tekstu. W pierwszej części rozpatrujemy dokładne warianty problemu znajdowania szablonów. W oryginalnym problemie szukamy takiego słowa, którego wystąpienia pokrywają dany tekst. W pracy „Efficient Computation of 2-covers of a String” analizowane jest pojęcie 2-szablonów, czyli par słów o tej samej długości, których wystąpienia pokrywają dany tekst. W pracy przedstawiamy algorytm znajdujący dla każdej długości k przykładowy 2-szablon długości k (jeśli dla niej takowy istnieje) w oczekiwanym czasie O(n log n log log n) i pamięci O(n). „Shortest Covers of All Cyclic Shifts of a String” rozwiązuje problem znalezienia najkrótszych szablonów dla wszystkich cyklicznych przesunięć w czasie O(n log n) i pamięci O(n). Dodatkowo, opracowany jest tam bardzo dokładny opis zbioru długości najkrótszych szablonów wszystkich cyklicznych przesunięć słów Fibonacciego. W pracy „Internal Quasiperiod Queries” pokazujemy jak efektywnie odpowiadać na zapytania wewnętrzne o najkrótsze i wszystkie szablony. Opracowana struktura danych pozwala na znalezienie najkrótszego szablonu na przedziale w czasie O(log n log log n) lub wszystkich szablonów w czasie O(log n (log log n)^2). Struktura danych potrzebuje O(n log n) pamięci i O(n log n) czasu obliczeń wstępnych. Dodatkowo, przedstawione są efektywne rozwiązania w modelu offline. W pracy „String Covers of a Tree” analizowane jest naturalne uogólnienie szablonu, w którym pokrywamy nie słowo, a drzewo. Krawędzie są etykietowane literami. Etykietą ścieżki jest słowo będące sekwencją liter na przechodzonych krawędziach. Słowo nazywamy szablonem drzewa, jeśli ścieżki etykietowane tym słowem pokrywają całe drzewo. Dla skierowanego drzewa przedstawiamy algorytm znajdujący wszystkie szablony w czasie O(n log n log log n), a w przypadku nieskierowanym w czasie i pamięci O(n^2). Dodatkowo, w przypadku nieskierowanym przedstawiamy alternatywny algorytm używający tylko O(n) pamięci, lecz działający w czasie O(n^2 log n). W drugiej części rozprawy przedstawiamy asymptotycznie efektywne rozwiązania do praktycznych problemów. W pracy ``Efficient Computation of Sequence Mappability'' rozważany jest problem mapowalności. Musimy w nim policzyć dla każdego indeksu i, będącego początkiem podsłowa długości m, na ilu innych indeksach znajduje się pasujące podsłowo tej samej długości, dopuszczając do k niedopasowań. Przedstawiamy kilka wyników, z których głównym jest algorytm działający w czasie O(n min{log^k n, m^k}) i pamięci O(n) dla ustalonego k. Dodatkowo, pokazujemy, że nie można rozwiązać problemu mapowalności w ściśle subkwadratowym czasie, chyba że hipoteza Strong Exponential Time jest nieprawdziwa. W pracy „Circular Pattern Matching with k Mismatches” analizujemy wariant wyszukiwania wzorca, w którym wzorzec może być dowolnie przesuwany cyklicznie i dopuszczamy do k niedopasowań. Przedstawiamy prosty algorytm działający w czasie O(nk) i pamięci O(m) i bardziej skomplikowany algorytm O(n + nk^4/m), działający również w pamięci O(m). Wyniki często bazują na analizie okresowości i użyciu zarówno klasycznych narzędzi stringologicznych, jak i najnowocześniejszych, zaawansowanych struktur danych.

This thesis consists of several results in the field of algorithms on strings. In particular, we consider variants of string covers and pattern matching with mismatches. From now on, we will use n to denote the length of the input text. In the first part we consider exact variants of finding string covers, that is, testing whether a text can be generated by concatenations and superpositions of a shorter string. In “Efficient Computation of 2-covers of a String” we present an algorithm which tests whether a text can be generated by concatenations and superpositions of 2 strings of the same length. The algorithm works in O(n log n log log n) expected time and O(n) space. “Shortest Covers of All Cyclic Shifts of a String” solves the titular problem in O(n log n) time and O(n) space. It also provides a precise description of the set of lengths of the shortest covers of all cyclic shifts of Fibonacci words. “Internal Quasiperiod Queries” shows how to efficiently answer internal queries about various types of quasiperiod related queries. The paper presents an algorithm which allows to find the shortest cover on a given interval in O(log n log log n) or all covers in O(log n (log log n)^2) time and O(n log n) space. We also present more efficient solutions in the offline model. “String Covers of a Tree” considers a natural generalization of cover, where one can cover a tree with paths corresponding to the cover. The algorithm from the paper finds all covers in a directed tree in O(n log n / log log n) time and in the case of undirected tree in O(n^2) time and space. In the case of undirected tree we provide an alternative algorithm using O(n) space and O(n^2 log n) time. The second part of the thesis provides asymptotically efficient solutions to practical problems. “Efficient Computation of Sequence Mappability” considers a problem where one needs to compute mappability for each substring of length m with up to k mismatches. There, we provide a collection of results, most notably an O(n min { log^k n, m^k }) time and O(n) space algorithm for fixed k and that one cannot solve (k,m)-mappability in strongly subquadratic time unless Strong Exponential Time Hypothesis fails. “Circular Pattern Matching with k Mismatches” is a variant of pattern matching where we allow the pattern to be arbitrarily circularly shifted and up to k characters replaced. We provide a simple O(nk) time and O(m) space solution and more elaborate O(n + nk^4/m) time and O(m) space algorithm. The results usually exploit periodicity analysis and apply a mix of classic stringology tools and state-of-the-art data structures.