# Classical and Quantum Algorithms for Constructing Text from Dictionary Problem

arXiv: https://arxiv.org/abs/2005.14335 · HTML: https://mlsanity.com/paper/2005.14335/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2020.

## Built on by (most cited first, 1 of 1)

- [Quantum Algorithm for the Shortest Superstring Problem](https://mlsanity.com/paper/2112.13319/) (2021)

## Abstract (arXiv)

We study algorithms for solving the problem of constructing a text (long string) from a dictionary (sequence of small strings). The problem has an application in bioinformatics and has a connection with the Sequence assembly method for reconstructing a long DNA sequence from small fragments. The problem is constructing a string t of length n from strings s1,dots, sm with possible intersections. We provide a classical algorithm with running time Oleft(n+L +m(log n)2right)=tildeO(n+L) where L is the sum of lengths of s1,dots,sm. We provide a quantum algorithm with running time Oleft(n +log n·(log m+loglog n)· √m· Lright)=tildeOleft(n +√m· Lright). Additionally, we show that the lower bound for the classical algorithm is Omega(n+L). Thus, our classical algorithm is optimal up to a log factor, and our quantum algorithm shows speed-up comparing to any classical algorithm in a case of non-constant length of strings in the dictionary.