Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Quantum and classical algorithms for the multiple query version of the uniform multiple occurrences shortest common superstring problem

Abstract

We consider the SUM-SCS problem: given a dictionary of \(n\) strings, construct a shortest string containing at least \(k\) occurrences of dictionary strings. We study the multiple query version (MSUM-SCS): for a fixed dictionary, find the lengths of shortest superstrings for \(m\) values \(k_1,\dots ,k_m\). We consider the factor-free case when non of the strings can be substring of any another. We present a quantum algorithm with \(O^*(mn^{1.5}\log k_{\max }+n^{2.5}\log k_{\max }+L)\) complexity, a classical one with \(O^*(mn^{2}\log k_{\max }+n^{3}\log k_{\max }+L)\) complexity. Here \(L\) is the total length of the strings, \(k_{\max }=\max _{1\leq r\leq m} k_r\), and \(O^*\) notation hides not only a constant, but also polylogarithmic multiple, i.e. a polynomial on \(\log m, \log n,\log \log k_{\max }, \log L\) .

Keywords: strings, quantum algorithms, query complexity, shortest common superstring.

BibTeX
@article{IS-Khadiev-Kapralov-Ilikaev2026,
  author  = {Khadiev, Kamil Ravilevich and Kapralov, Ruslan Ilnarovich and Ilikaev, Artyom Rashitovich},
  title   = {{Quantum and classical algorithms for the multiple query version of the uniform multiple occurrences shortest common superstring problem}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {286--289},
}
AMSBIB
\Bibitem{IS-Khadiev-Kapralov-Ilikaev2026}
\by K.\,R.~Khadiev, R.\,I.~Kapralov, A.\,R.~Ilikaev
\paper Quantum and classical algorithms for the multiple query version of the uniform multiple occurrences shortest common superstring problem
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 286--289
\lang In Russian
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover