Diptarama, Ryo Yoshinaka and Ayumi Shinohara
Fast Full Permuted Pattern Matching Algorithms on Multi-track Strings
Abstract: |
A multi-track string is a tuple of strings of the same length. The full permuted pattern matching problem is, given two multi-track strings = (t_{1}, t_{2}, . . ., t_{N}) and = (p_{1}, p_{2}, . . ., p_{N}) such that |p_{1}|= ⸳ ⸳ ⸳ =|p_{N}| ≤ |t_{1}|= ⸳ ⸳ ⸳ =|t_{N}|, to find all positions i such that = (t_{r1}[i:i+m-1], ⸳ ⸳ ⸳, t_{rN}[i:i+m-1]) for some permutation (r_{1}, ⸳ ⸳ ⸳, r_{N}) of (1, ⸳ ⸳ ⸳, N), where m=|p_{1}| and $t[i:j] denotes the substring of t from position i to j. We propose new algorithms that perform full permuted pattern matching practically fast. The first and second algorithms are based on the Boyer-Moore algorithm and the Horspool algorithm, respectively. The third algorithm is based on the Aho-Corasick algorithm where we use a multi-track character instead of a single character in the so-called goto function. The fourth algorithm is an improvement of the multi-track Knuth-Morris-Pratt algorithm that uses an automaton instead of the failure function of the original algorithm. Our experiment results demonstrate that those algorithms perform permuted pattern matching faster than existing algorithms. |
Download paper: | |||
PostScript | BibTeX reference |
Download presentation: |