8 papers
Computing Smallest Suffixient Arrays in Sublinear Time
Hiroto Fujimaru, Gonzalo Navarro, Francisco Olivares +3
A suffixient array is a novel data structure that, when combined with an index providing direct access on a text , allows us to answer a variety of pattern matching queries. In…
Faster Algorithms for Longest Common Substring
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski +1
In the classic longest common substring (LCS) problem, we are given two strings and , each of length at most , over an alphabet of size , and we are asked to find a l…
Space-Efficient k-Mismatch Text Indexes
Tomasz Kociumaka, Jakub Radoszewski
A central task in string processing is text indexing, where the goal is to preprocess a text (a string of length ) into an efficient index (a data structure) supporting queries…
Subsequence Covers of Words
Panagiotis Charalampopoulos, Solon P. Pissis, Jakub Radoszewski +3
We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word is an s-cover of a word if the occurrences of in as subsequences cover…
Fast Computation of -Runs, Parameterized Squares, and Other Generalised Squares
Yuto Nakashima, Jakub Radoszewski, Tomasz WaleÅ
A -mismatch square is a string of the form where and are two equal-length strings that have at most mismatches. Kolpakov and Kucherov [Theor. Comput. Sci., 2003…
Counting Distinct Square Substrings in Sublinear Time
Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski +3
We show that the number of distinct squares in a packed string of length over an alphabet of size can be computed in time in the word-RAM model. This paper…