System and method for regular expression matching with multi-strings and intervals

1. 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.

2. The method of claim 1 , wherein the end occurrence of one substring is the start state for another substring.

3. The method of claim 1 , the method further comprising returning a regular expression result based on the matching instance entered in the regular expression matching process.

4. The method of claim 1 , wherein the stream of start states and the stream of end occurrences are bit streams.

5. The method of claim 1 , wherein the input string comprises one of alphanumeric characters and punctuation.

6. The method of claim 1 , wherein characters in the input string represent proteins.

7. The method of claim 1 , wherein the stream of start states is represented as a finite state automaton.

8. The method of claim 1 , wherein the substrings have a substring length less than a length of the input string.

9. A system comprising:

a processor; and

a computer-readable storage medium having instructions stored which, when executed on the processor, cause the processor to perform operations comprising:

identifying in an input string 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 the 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.

10. The system of claim 9 , wherein the stream of end occurrences is associated with multi-string matching in the input string.

11. The system of claim 9 , wherein the stream of start states is represented as a finite state automaton.

12. A computer-readable storage device having instructions stored which, when executed by a computing device, cause the computing device to perform operations comprising:

identifying in an input string 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 the regular expression matching process, wherein the start states in the stream of start states are developed in parallel;

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.

13. The computer-readable storage device of claim 12 , wherein the stream of end occurrences is associated with multi-string matching in the input string.

14. The computer-readable storage device of claim 12 , the computer-readable storage device having additional instructions stored which result in the operations further comprising returning a regular expression result based on the matching instance entered in the regular expression matching process.