Online pattern matching with wildcards

In this paper we present a new algorithm to handle the pattern matching problem where the pattern can contain flexible wildcards. Given a sequence S and a pattern P consisting of subpatterns separated by flexible wildcards, the problem is to find P´s all occurrences with exact match positions under the one-off condition and length constraints. We propose an algorithm, PMW that locates each subpattern of P in S as soon as it appears in S in O(m+n+f(GM+α)) time with O(m+A) space overhead. Compared to the previous peers theoretical analysis and experimental results show that PMW is more competitive. It has an advantage on both the time and space complexities. It also has better stability with the increasing of the maximum gap constraints or the number of subpatterns.