36 citations · 78 across the 32 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.DS2021
Hardness of Detecting Abelian and Additive Square Factors in Strings
Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński +2
We prove 3SUM-hardness (no strongly subquadratic-time algorithm, assuming the 3SUM conjecture) of several problems related to finding Abelian square and additive square factors in…
cs.DS2021
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 lo…