Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.

DOI10.4230/LIPIcs.CPM.2016.8zbMath1380.68477OpenAlexW2554909279MaRDI QIDQ5369541

Costas S. Iliopoulos, Jakub Radoszewski

Publication date: 17 October 2017

Full work available at URL: https://doi.org/10.4230/lipics.cpm.2016.8

zbMATH Keywords

partial wordindeterminate stringprefix arraystring with don't careslongest common conservative prefix queries

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Related Items (8)

Covering problems for partial words and for indeterminate strings ⋮ Maximal degenerate palindromes with gaps and mismatches ⋮ Algorithms and complexity on indexing founder graphs ⋮ String Covering: A Survey ⋮ Unnamed Item ⋮ Approximate pattern matching on elastic-degenerate text ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Comparing Degenerate Strings

This page was built for publication: Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.