Quantum algorithms for longest common and palindromic substrings in the circuit model

The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) problems are fundamental challenges in string processing, traditionally solved in linear time using classical computation through suffix trees. Recent breakthroughs by Le Gall and Seddighin [1] introduced sublinear quantum query algorithms, while Akmal and Jin [2] further improved the LCS complexity to O˜(n2/3). While these results are remarkable in the quantum query model, their practical implementation on real quantum hardware remains elusive. In this paper, we bridge this gap by presenting the first O˜(n) quantum algorithms for both LCS and LPS in the circuit model of computation. Our circuits are explicitly constructed and analyzed in terms of size and depth, achieving polylogarithmic overheads while preserving the O˜(n) depth bound. This provides, for the first time, concrete circuit-level blueprints and resource estimates for quantum solutions to LCS and LPS.