Jumbled matching with SIMD

Sukhpal Ghuman, Jorma Tarhio

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


Jumbled pattern matching addresses the problem of finding all permuted occurrences of a substring in a text. We introduce two improved algorithms for exact jumbled matching of short patterns. Our solutions apply SIMD (Single Instruction Multiple Data) computation in order to quickly filter the text. One of them utilizes the equal any operation and the other searches for the least frequent character of the pattern. Our experiments show that the best algorithm is 30% faster than previous algorithms for short English patterns.
Original languageEnglish
Title of host publicationPrague Stringology Conference 2016, August 29-31, 2016
EditorsJan Holub, Jan Zdarek
Place of PublicationPrague, Czech Republic
PublisherCzech Technical University in Prague
ISBN (Print)978-80-01-05996-8
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventPrague Stringology Conference - Prague, Czech Republic
Duration: 29 Aug 201631 Aug 2016


ConferencePrague Stringology Conference
Abbreviated titlePSC
Country/TerritoryCzech Republic


Dive into the research topics of 'Jumbled matching with SIMD'. Together they form a unique fingerprint.

Cite this