Improved online algorithms for jumbled matching

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • Sheridan College Institute of Technology and Advanced Learning
  • Seneca College of Applied Arts & Technology

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.

Details

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

    Research areas

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

ID: 26409302