Quantum String Matching Unfolded and Extended

Abstract

The string matching problem is one of the fundamental problems in computer science with applications in a variety of fields. Basically, it consists in finding all occurrences of a given pattern within a larger text. Despite its straightforward formulation, it has given rise to a huge number of solutions based on very different approaches and varied computational paradigms. But it is only very recently that the first solution based on quantum computation has been proposed by Niroula and Nam, allowing the problem to be solved in O(n(log2(n)+log(m))) time, with a quadratic speed-up compared to classical computation. To date, these two research fields have remained almost entirely separate, mainly because the technical aspects typical of the quantum computation field remain almost obscure to those involved in text processing. This paper aims to reconcile the two fields by unfolding the technical aspects of the Niroula-Nam quantum solution and providing a detailed general procedure working in O(nlog2(n)) time that can be used as a framework for solving other string matching problems, including nonstandard ones. In this direction, the paper also proposes an extension of the algorithm to the approximate string matching problem with swaps, reporting the configuration of the occurrence together with its position, and achieving a quasi-linear O(nlog2(n)) time complexity when m= O(log (n)).