Searching All including Overlapping Matches through Regular Expressions
Wojciech Wieczorek, Arkadiusz Nowakowski, Łukasz Strąk · Procedia Computer Science · 2025
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.