Regular expression matching

A non-transitory machine-readable storage medium storing instructions for matching a regular expression to a string, the instructions executable by a processor of a computing device to cause the processor to:

• generate a data structure based on a non-deterministic finite automaton (NFA) that represents the regular expression, wherein the data structure initially includes a first state that includes a set of segments, each segment indicating a segment starting state of the NFA, and each segment representing zero or more consecutive states of the NFA starting at the segment starting state, and wherein different segments of the set of segments are capable of indicating different segment starting states on the NFA, and wherein each segment represents a partial match of the regular expression to the string;
• analyze the string in relation to the NFA, wherein a pointer is maintained to a currently analyzed character of the string;
• and
• modify the data structure as the string is analyzed, such modification including adding states to the data structure as characters of the string are matched to states of the NFA.

A system, comprising:

• at least one repository to store a string, a non-deterministic finite automaton (NFA) that represents a regular expression, and a data structure based on the NFA, wherein the data structure includes a set of segments, each segment indicating a segment starting state of the NFA, and each segment representing zero or more consecutive states of the NFA starting at the segment starting state, and wherein different segments of the set of segments are capable of indicating different segment starting states on the NFA, and wherein each segment represents a partial match of the regular expression to the string;
• a processor;
• and
• a memory storing instructions that when executed cause the processor to match the regular expression to the string, wherein to match the regular expression to the string, the instructions are to cause the processor to analyze the string in relation to the NFA and modify the data structure as the string is analyzed, such modification including attempting to expand at least one of the segments in the set to represent additional states of the NFA.