3 papers
cs.DS2025
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…
cs.DS2025
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…
cs.DS2025
Approximate Circular Pattern Matching
Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski +4
We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length- text , a length- pattern , and a…