Prague Stringology Conference 2019
Avivit Levy and B. Riva Shalom
Online Parameterized Dictionary Matching with One Gap
| Abstract: |
| We study the online Parameterized Dictionary Matching with One Gap problem (PDMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can match any string, so that given a text that arrives online, a character at a time, we can report all of the patterns from D that parameterized match to suffixes of the text that has arrived so far, before the next character arrives. Two equal-length strings are a parameterized match if there exists a bijection on the alphabets, such that one string matches the other under the bijection. The gap symbols are associated with bounds determining the possible lengths of matching strings. Online Dictionary Matching with One Gap (DMOG) captures the difficulty in a bottleneck procedure for cyber-security, as many digital signatures of viruses manifest themselves as patterns with a single gap. Parameterized match captures possible encryption of the patterns. We also define and study the strict PDMOG problem, in which sub-patterns of the same dictionary pattern should be parameterized matched via the same bijection. This captures situations where sub-patterns of a dictionary pattern are encoded simultaneously. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |