Flexible and Efficient Algorithms for Abelian Matching in Strings

03/07/2018
by   Simone Faro, et al.
0

The abelian pattern matching problem consists in finding all substrings of a text which are permutations of a given pattern. This problem finds application in many areas and can be solved in linear time by a naive sliding window approach. In this short communication we present a new class of algorithms based on a new efficient fingerprint computation approach, called Heap-Counting, which turns out to be fast, flexible and easy to be implemented. It can be proved that our solutions have a linear worst case time complexity and, in addition, we present an extensive experimental evaluation which shows that our newly presented algorithms are among the most efficient and flexible solutions in practice for the abelian matching problem in strings.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset