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

DOI10.4230/LIPICS.CPM.2016.8MaRDI QIDQ5369541zbMATH OpenOpenAlexFDO

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

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)

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

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)