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

DOI10.4230/LIPICS.CPM.2016.8zbMATH Open1380.68477OpenAlexW2554909279MaRDI QIDQ5369541FDOQ5369541

Authors: Costas S. Iliopoulos, Jakub Radoszewski 

Publication date: 17 October 2017

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

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Lower bounds of temporal and spatial complexity of the substring search problem
• Shortest unique substrings queries in optimal time
• Subquadratic-time algorithms for abelian stringology problems
• Combinatorial Pattern Matching
• A sublinear time string prefix square detection algorithm
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Efficient detection of quasiperiodicities in strings

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)

Cited In (7)

• Approximate pattern matching on elastic-degenerate text
• String Covering: A Survey
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Comparing Degenerate Strings
• Degenerate string comparison and applications
• Algorithms and complexity on indexing founder graphs
• Maximal degenerate palindromes with gaps and mismatches

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369541)