Negative regular expression search operations

A method performed by a content search system for determining whether an input string of characters matches a negative regular expression that includes a positive pattern and a negative pattern, comprising:

• comparing, in a content addressable memory (CAM) device, a first portion of the input string with the positive pattern to generate a match signal, wherein the CAM device contains a plurality of CAM rows that store a data word chain, and wherein the data word, chain corresponds to the negative regular expression and spans multiple non-contiguous CAM, rows;
• comparing, in the CAM device, a second portion of the input string with the negative pattern to generate a mismatch signal;
• and
• indicating a match condition between the input string and the negative regular expression if the match signal indicates a match between the first portion and the positive pattern and if the mismatch signal indicates a mismatch between the second portion and the negative pattern.

A content search system for determining whether an input string of characters matches a negative regular expression that includes a positive pattern and a negative pattern, comprising:

• means for comparing a first portion of the input string with the positive pattern to generate a match signal;
• means for comparing a second portion of the input string with the negative pattern to generate a mismatch signal;
• and
• means for indicating a match condition between the input string and the negative regular expression if the match signal indicates a match between the first portion and the positive pattern and if the mismatch signal indicates a mismatch between the second portion and the negative pattern, wherein the means for comparing the first portion and the means for comparing the second portion comprise a content addressable memory (CAM) device, that contains a plurality of CAM rows that store a data word chain, wherein the data word chain corresponds to the negative regular expression and spans multiple non-contiguous CAM rows.