5 papers
Longest Unbordered Factor in Quasilinear Time
Tomasz Kociumaka, Ritu Kundu, Manal Mohamed +1
A border u of a word w is a proper factor of w occurring both as a prefix and as a suffix. The maximal unbordered factor of w is the longest factor of w which does not have a borde…
Efficient Pattern Matching in Elastic-Degenerate Strings
Costas Iliopoulos, Ritu Kundu, Solon Pissis
In this paper, we extend the notion of gapped strings to elastic-degenerate strings. An elastic-degenerate string can been seen as an ordered collection of k > 1 seeds (substrings/…
Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +5
Longest common extension queries (LCE queries) and runs are ubiquitous in algorithmic stringology. Linear-time algorithms computing runs and preprocessing for constant-time LCE que…
Linear Algorithm for Conservative Degenerate Pattern Matching
Maxime Crochemore, Costas S. Iliopoulos, Ritu Kundu +2
A degenerate symbol x* over an alphabet A is a non-empty subset of A, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its n…
Linear-Time Superbubble Identification Algorithm for Genome Assembly
Ljiljana Brankovic, Costas S. Iliopoulos, Ritu Kundu +3
DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biologica…