2 papers
cs.DS2026
Dynamic Longest Common Substring in Polylogarithmic Time
Panagiotis Charalampopoulos, PaweÅ Gawrychowski, Karol Pokorski
The longest common substring problem consists in finding a longest string that appears as a (contiguous) substring of two input strings. We consider the dynamic variant of this pro…
cs.DS2025
Faster ED-String Matching with Mismatches
PaweŠGawrychowski, Adam Górkiewicz, Pola Marciniak +2
We revisit the complexity of approximate pattern matching in an elastic-degenerate string. Such a string is a sequence of finite sets of strings of total length , and compac…