Improved online algorithms for jumbled matching

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Tutkijat

Organisaatiot

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

Kuvaus

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.

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut1-13
JulkaisuDiscrete Applied Mathematics
TilaSähköinen julkaisu (e-pub) ennen painettua julkistusta - 1 tammikuuta 2018
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

ID: 26409302