Tuning Algorithms for Jumbled Matching
Tamanna Chhabra, Sukhpal Singh Ghuman, Jorma Tarhio · Prague Stringology Conference · 2015
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. Most of our algorithms are variations of earlier algorithms. We show by practical experiments that our algorithms are competitive with the previous solutions.