Backtracking
When regular expressions have optional or alternative matching patterns, the regular expression matching engine, at some point in its evaluation of an input string, can branch in one or more directions to accomplish all possible matches. If the match is not successful in the first direction the engine searches, it must back up its position in the input string to where the branch occurred and try an alternative match.
For instance, consider a regular expression designed to match the two spellings of the color gray: gray and grey. The alternation character | is used to create the regular expression gr(a|e)y, which can match either spelling. When applied to the input string greengraygrowngrey, assume the engine first tries to match gray. It matches the first two characters in the input string, gr, then fails at the e in green. It backtracks to r (the last successful match before the alternative character) and tries to match grey. Failing at the second e, the engine continues searching and will ultimately match the two embedded words gray and grey.
The following code example shows how to create this regular expression and apply it to the input string.
' Define strings: "gray" and "grey".
Dim r As New Regex("gr(a|e)y")
Dim m As MatchCollection = r.Matches("greengraygrowngrey")
Console.WriteLine("Number of groups found = " & m.Count.ToString())
[C#]
// Define strings: "gray" and "grey".
Regex r = new Regex("gr(a|e)y");
MatchCollection m = r.Matches("greengraygrowngrey");
Console.WriteLine("Number of groups found = " + m.Count.ToString ());