Paper Info
Title
Permuted Pattern Matching Algorithms on Multi-Track Strings
Abstract
A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this paper, we propose several algorithms for permuted pattern matching. Our first algorithm, which is based on the Knuth-Morris-Pratt (KMP) algorithm, has a fast theoretical computing time with O(mk) as the preprocessing time and O(nklog sigma)as the matching time, where n, m, k, sigma, and occdenote the length of the text, the length of the pattern, the number of strings in the multi-track, the alphabet size, and the number of occurrences of the pattern, respectively. We then improve the KMP-based algorithm by using an automaton, which has a better experimental running time. The next proposed algorithms are based on the Boyer-Moore algorithm and the Horspool algorithm that try to perform pattern matching. These algorithms are the fastest experimental algorithms. Furthermore, we propose an extension of the AC-automaton algorithm that can solve dictionary matching on multi-tracks, which is a task to find multiple multi-track patterns in a multi-track text. Finally, we propose filtering algorithms that can perform permuted pattern matching quickly in practice.
Year
DOI
Venue
2019
10.3390/a12040073
ALGORITHMS
Keywords
Field
DocType
multi-track string,permuted pattern matching,AC-automaton
Tuple,Permutation,Automaton,Filter (signal processing),Algorithm,Preprocessor,Artificial intelligence,Boyer–Moore–Horspool algorithm,Pattern matching,Machine learning,Mathematics,Alphabet
Journal
Volume
Issue
ISSN
12
4
1999-4893
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Diptarama Hendrian102.70
Yohei Ueki200.34
Kazuyuki Narisawa3336.82
Ryo Yoshinaka417226.19
Ayumi Shinohara593688.28