Bit-parallel approximate matching of circular strings with k mismatches

Tommi Hirvola, Jorma Tarhio

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)


We consider approximate string matching of a circular pattern consisting of the rotations of a pattern of length m. From SBNDM and Tuned Shift-Add, we derive a sublinear-time algorithm for searching a noncircular pattern with k allowed mismatches, which is extended to the problem of approximate circular pattern matching with k mismatches. We prove that the presented algorithms are average-optimal for m⋅⌈log2(k+1)+1⌉ = O(w), where w is the size of the computer word in bits. Experiments conducted under the aforementioned condition show that the new k-mismatches algorithm for circular strings outperforms previous solutions in practice. In particular, our algorithm is the first nonfiltering method for approximate circular string matching in sublinear average time, which makes it more suitable than earlier filtering methods for high error levels k/m and small alphabets.
Original languageEnglish
Article number1.5
Pages (from-to)1-12
Number of pages12
JournalACM Journal of Experimental Algorithmics
Issue number1
Publication statusPublished - Dec 2017
MoE publication typeA1 Journal article-refereed


  • approximate string matching
  • circular strings
  • bit-parallel automata


Dive into the research topics of 'Bit-parallel approximate matching of circular strings with k mismatches'. Together they form a unique fingerprint.

Cite this