Online Abelian Pattern Matching
Suggested citation:
Ejaz, T., S. Rahmann, & J. Stoye. 2008. Online Abelian Pattern Matching. Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld Bielefeld: Technische Fakultät der Universität Bielefeld.
Authors:
Ejaz, Tahir
;
Rahmann, Sven
;
Stoye, Jens
Department:
Technische Fakultät
AG Genominformatik
Institut für Bioinformatik
Abstract:
An abelian pattern describes the set of strings that comprise of the same combination of characters. Given an abelian pattern P and a text T [Epsilon] [Sigma]^n, the task is to find all occurrences of P in T, i.e. all substrings S = T_i...T_j such that the frequency of each character in S matches the specified frequency of that character in P.
In this report we present simple online algorithms for abelian pattern matching, and give a lower bound for online algorithms which is [Omega](n).
Keywords:
Compomers ;
Permutation patterns ;
Online algorithms ;
Abelian patterns ;
Pattern matching ;
String matching
Publication Language:
English
PDF
Google Scholar
BASE
Google
Bookmark