Flexible and Efficient Algorithms for Abelian Matching in Strings
This work provides a practical solution for string processing tasks in various application areas, though it appears incremental as it builds upon existing linear-time methods.
The authors tackled the abelian pattern matching problem by introducing a new class of algorithms based on the Heap-Counting fingerprint computation approach, achieving linear worst-case time complexity and demonstrating through experiments that these algorithms are among the most efficient and flexible in practice.
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.