Searching All including Overlapping Matches through Regular Expressions

In this paper, we explore the problem of finding all substrings, including those that overlap with others, that match given regular expressions in a long text. The standard methods (like finditer in Python or NextMatch in C#) are inefficient for the task due to the challenging requirement of finding all possible overlaps. We propose two new methods to tackle the problem: an efficient one based on automata and a suffix tree and an enhanced naive solution based solely on automata. Our approaches were evaluated in a series of experiments against each other.