Patent ID: 8843508

Claim:
A method comprising: identifying in an input string, via a processor, substrings, the substrings generated by one of a regular expression matching process and a multi-string matching process; receiving a stream of start states for each of the substrings generated according to a regular expression matching process; receiving a stream of end occurrences for each of the substrings generated according to the multi-string matching process; identifying, via an algorithm, an instance where an end occurrence of a particular substring matches the start state of the particular substring, to yield a matching instance, wherein the algorithm encodes variable length gaps into the stream of start states using a number of bits proportional to an upper bound on a length of the substrings, and wherein identifying the instance where an end occurrence of a particular substring matches a start state of the particular substring is further based on a bit offset between the stream of start states and the stream of end occurrences, where the bit offset for each substring is a size of the particular substring; and entering the matching instance as a positive substring accept state in the regular expression matching process on the input string.