Elastic-degenerate string comparison
Estéban Gabory, Moses Njagi Mwaniki, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski, Michelle Sweering, Wiktor Zuba · Information and Computation · 2025
An elastic-degenerate (ED) string T is a sequence of n sets T [ 1 ] , … , T [ n ] containing m strings in total whose cumulative length is N . We call n , m , and N the length, the cardinality and the size of T , respectively. The language of T is defined as L ( T ) = { S 1 ⋯ S n : S i ∈ T [ i ] for all i ∈ [ 1 , n ] } . Given two ED strings, how fast can we check whether the two languages they represent have a nonempty intersection? We call this problem the ED String Intersection (EDSI) problem. For two ED strings T 1 and T 2 of lengths n 1 and n 2 , cardinalities m 1 and m 2 , and sizes N 1 and N 2 , respectively, we show the following: • There is no O ( ( N 1 N 2 ) 1 − ϵ ) -time algorithm, for any ϵ > 0 , for EDSI even if T 1 and T 2 are over a binary alphabet, unless the Strong Exponential-Time Hypothesis is false. • There is no combinatorial O ( ( N 1 + N 2 ) 1.2 − ϵ f ( n 1 , n 2 ) ) -time algorithm, for any ϵ > 0 and any function f , for EDSI even if T 1 and T 2 are over a binary alphabet, unless the Boolean Matrix Multiplication conjecture is false. • An O ( N 1 log N 1 log n 1 + N 2 log N 2 log n 2 ) -time algorithm for outputting a compact representation of the intersection language of two unary ED strings. When T 1 and T 2 are given in a compact representation, we show that the problem is NP-complete. • An O ( N 1 m 2 + N 2 m 1 ) -time algorithm for EDSI. • An O ˜ ( N 1 ω − 1 n 2 + N 2 ω − 1 n 1 ) -time algorithm for EDSI, where ω is the matrix multiplication exponent; the O ˜ notation suppresses factors that are polylogarithmic in the input size.