1 citations · 2 across the 15 of their papers we have counts for
23 papers · 1 filter
MacCorles: Minimum Alignment Cost Computation on Run-Length Encoded Strings
Wing-Kai Hon, Dominik Köppl, Jun-Hong Wang
We study a tie-breaking variant of the longest common subsequence problem on run-length encoded strings. Given two strings, the goal is first to maximize the number of equal aligne…
Indexing Range Maximum-Sum Segment Queries with Offsets
Seungbum Jo, Dominik Köppl
Given an array of real numbers, the maximum segment sum (MSS) problem is to find a contiguous subarray that has the largest sum. While the MSS problem can be solved optimally w…
Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes
Paola Bonizzoni, Younan Gao, Dominik Köppl +1
We revisit the online construction of \emph{smallest suffixient sets} and the online computation of the \emph{longest repeating suffix} (LRS). We give the first compressed-space on…
Compact multi-text index for circular Cartesian tree matching
Roman Pauli, Eric Osterkamp, Dominik Köppl
Cartesian tree matching (CTM) is a structural pattern matching approach that identifies sequences with the same Cartesian tree topology, making it suitable for data with natural va…
Smallest suffixient set maintenance in near-real-time
Dominik Köppl, Gregory Kucherov
The size of the \textit{smallest suffixient set} of positions of a string recently emerged as a new measure of string \textit{repetitiveness} -- a measure reflecting how much of re…
Counting Distinct (Non-)Crossing Substrings in Optimal Time
Haruki Umezaki, Hiroki Shibata, Dominik Köppl +3
Let be a string of length . The problem of counting factors crossing a position -- Problem 64 from the textbook ``125 Problems in Text Algorithms'' [Crochemore, Lecroq, and…