Abelian pattern matching in strings
Loading...
Date
2010-06-29
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Abelian pattern matching is a new class of pattern matching problems. In
abelian patterns, the order of the characters in the substrings does not matter,
e.g. the strings abbc and babc represent the same abelian pattern a+2b+c.
Therefore, unlike classical pattern matching, we do not look for an exact
(ordered) occurrence of a substring, rather the aim here is to find any permutation
of a given combination of characters that represents the given
abelian pattern.
In this thesis, we study the problem of abelian pattern matching in strings
in a systematic manner, and present several algorithms for exact as well as
approximate abelian pattern matching. We also present different strategies
for indexing the input text to make the abelian pattern matching more efficient.
Description
Table of contents
Keywords
Abelian patterns, permutation patterns, pattern matching