Circular string matching revisited
Carl Barton, Costas S. Iliopoulos, Solon P. Pissis · Research Portal (King's College London) · 2013
Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist optimal average-case algorithms for exact circular string matching. In this article, we present a suboptimal average-case algorithm for exact circular string matching requiring time and space O(n). However, we anticipate that this can be easily adapted to deal with approximate circular string matching with k-mismatches, under the Hamming distance model, with no additional cost in time or space complexity for moderate values of k.