English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS)are classical problems in computer science, representing fundamental challengesin string processing. Both problems can be solved in linear time using aclassical model of computation, by means of very similar algorithms, bothrelying on the use of suffix trees. Very recently, two sublinear algorithms forLCS and LPS in the quantum query model have been presented by Le Gall andSeddighin~\cite{GallS23}, requiring $\tilde{\mathcal{O}}(n^{5/6})$ and$\tilde{\mathcal{O}}(\sqrt{n})$ queries, respectively. However, while the querymodel is fascinating from a theoretical standpoint, its practical applicabilitybecomes limited when it comes to crafting algorithms meant for actual executionon real hardware. In this paper we present, for the first time, a$\tilde{\mathcal{O}}(\sqrt{n})$ quantum algorithm for both LCS and LPS workingin the circuit model of computation. Our solutions are simpler than previousones and can be easily translated into quantum procedures. We also presentactual implementations of the two algorithms as quantum circuits working in$\mathcal{O}(\sqrt{n}\log^5(n))$ and $\mathcal{O}(\sqrt{n}\log^4(n))$ time,respectively.

Longest Common Substring and Longest Palindromic Substring in $\tilde{\mathcal{O}}(\sqrt{n})$ Time