Patent attributes
Example embodiments relate to regular expression matching. An example method may include generating a data structure based on a non-deterministic finite automaton (NFA) that represents a regular expression. The data structure may include a set of segments where each segment indicates a segment starting state of the NFA. Each segment may represent zero or more consecutive states of the NFA starting at the segment starting state. Different segments of the set of segments may be capable of indicating different segment starting states on the NFA. Each segment may represent a partial match of the regular expression to the string. The method may further include analyzing the string in relation to the NFA. The method may further include modifying the data structure as the string is analyzed. Such modification may include attempting to expand at least one of the segments in the set to represent additional states of the NFA.
