Patent ID: 7853578

Claim:
An apparatus for detecting a pattern in a string, wherein the pattern and the string each comprise one or more characters selected from a finite set of the one or more characters, wherein the string is N characters in length and the pattern is M characters in length, and wherein N≧M, the apparatus comprising: a ternary content-addressable memory (TCAM) comprising a first plurality of rows each storing a segment comprising W−S consecutive ones of the M characters in the pattern preceded by S don't-care characters, wherein zero≧S<W; a random-access memory to store a value of S for each of the first plurality of rows of the TCAM; and a controller to generate keys based on the string, wherein each of the keys includes consecutive ones of the N characters in a window of W characters of the string, the controller to apply the keys to the TCAM, wherein, when the TCAM returns a first matching row having a shift of S>zero in response to a first of the keys, the controller shifts the window right S places and generates a second of the keys including the consecutive ones of the N characters in the window that was shifted, wherein, when the TCAM returns a second matching row having a shift of S=zero, the controller declares a first initial match between the pattern and the string, wherein after the controller declares the first initial match between the pattern and the string, and when N>W, (a) the controller shifts the window right W places and generates the second of the keys including the consecutive ones of the N characters in the window that was shifted, (b) the controller applies the second of the keys to the TCAM, (c) wherein, when the TCAM returns the first matching row having a shift of S>zero, the controller declares no match between the pattern and the string, (d) wherein, when the TCAM returns the second matching row having a shift of S=zero, the controller repeats (a) through (c) until all of the M characters of the pattern have been applied to the TCAM, (e) when all keys in (a) through (d) return a shift of S=zero, the controller declares a complete match between the pattern and the string, and wherein S is an integer greater than or equal to zero, and M, W and N are integers greater than or equal to 1.