A note on quantum divide and conquer for minimal string rotation

DOI10.1016/J.TCS.2025.115120MaRDI QIDQ7014488zbMATH OpenFDO

Authors Qisheng Wang

Publication date 11 March 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115120

zbMATH Keywords

minimal string rotationquantum algorithmsquantum computingquantum query complexitystring processing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Algorithms on strings (68W32)

Cites work

• A course in combinatorics.
• A fast average case algorithm for lyndon decomposition
• A fast equivalence-checking algorithm for circular lists
• A quantum query complexity trichotomy for regular languages
• A surprisingly simple de Bruijn sequence construction
• Algorithms on Strings
• Algorithms on Strings, Trees and Sequences
• Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
• Automata for branching and layered temporal structures. An investigation into regularities of infinite transition systems
• Description and analysis of a bottom-up DFA minimization algorithm
• Deterministic Sampling–A New Technique for Fast Pattern Matching
• Factorizing words over an ordered alphabet
• Fast canonization of circular strings
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 4155884 (Why is no real title available?)
• scientific article; zbMATH DE number 4045190 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2038718 (Why is no real title available?)
• scientific article; zbMATH DE number 801745 (Why is no real title available?)
• Lexicographically least circular substrings
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• Near-optimal quantum algorithms for string problems
• On maximal suffixes and constant-space linear-time versions of KMP algorithm.
• Optimal algorithms for computing the canonical form of a circular string
• Quantum algorithm for lexicographically minimal string rotation
• Quantum meets fine-grained complexity: sublinear time quantum algorithms for string problems
• Quantum pattern matching fast on average
• Quantum Query Complexity of Some Graph Problems
• Reconstructing strings from substrings with quantum queries
• String matching in O( n+ m) quantum time
• String-matching on ordered alphabets
• The standard factorization of Lyndon words: an average point of view

Cited in

(2)

• Double-ended palindromic trees in linear time
• On the quantum time complexity of divide and conquer

This page was built for publication: A note on quantum divide and conquer for minimal string rotation

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