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.
| Original language | English |
|---|---|
| Title of host publication | Prague Stringology Conference 2016, August 29-31, 2016 |
| Editors | Jan Holub, Jan Zdarek |
| Place of Publication | Prague, Czech Republic |
| Publisher | Czech Technical University in Prague |
| Pages | 114-124 |
| ISBN (Print) | 978-80-01-05996-8 |
| Publication status | Published - 2016 |
| MoE publication type | A4 Article in a conference publication |
| Event | Prague Stringology Conference - Prague, Czech Republic Duration: 29 Aug 2016 → 31 Aug 2016 |
Conference
| Conference | Prague Stringology Conference |
|---|---|
| Abbreviated title | PSC |
| Country/Territory | Czech Republic |
| City | Prague |
| Period | 29/08/2016 → 31/08/2016 |