Permuted Pattern Matching Algorithms on Multi-Track Strings

Autor: Yohei Ueki, Kazuyuki Narisawa, Ryo Yoshinaka, Diptarama Hendrian, Ayumi Shinohara
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Zdroj: Algorithms, Vol 12, Iss 4, p 73 (2019)
Algorithms
Volume 12
Issue 4
ISSN: 1999-4893
Popis: 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&ndash
Morris&ndash
Pratt (KMP) algorithm, has a fast theoretical computing time with O ( m k ) as the preprocessing time and O ( n k log &sigma
) as the matching time, where n, m, k, &sigma
and denote 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&ndash
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.
Databáze: OpenAIRE
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje