Prague Stringology Conference 2016
Sukhpal Singh Ghuman and Jorma Tarhio
Jumbled Matching with SIMD
| Abstract: |
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |