Improved online algorithms for jumbled matching

Sukhpal Singh Ghuman, Jorma Tarhio*, Tamanna Chhabra

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We consider the problem of jumbled matching where the objective is to find all permuted occurrences of a pattern in a text. Besides exact matching we study approximate matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bit-parallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions.

Original languageEnglish
Pages (from-to)1-13
JournalDiscrete Applied Mathematics
DOIs
Publication statusE-pub ahead of print - 1 Jan 2018
MoE publication typeA1 Journal article-refereed

Keywords

  • Abelian matching
  • Algorithm engineering
  • Approximate string matching
  • Comparison of algorithms
  • Jumbled matching
  • SIMD computation

Fingerprint Dive into the research topics of 'Improved online algorithms for jumbled matching'. Together they form a unique fingerprint.

  • Cite this