Attempt to match from first character in Text Text: tantatsi Pattern: t matches ta matches, end of pattern ----------------------------------------------- Attempt to match from third character in Text Text: tantatsi Pattern: t does not match ----------------------------------------------- Attempt to match from fourth character in Text Text: tantatsi Pattern: t matches ta matches, end of pattern ----------------------------------------------- Attempt to match from sixth character in Text Text: tantatsi Pattern: t matches ta does not match ----------------------------------------------- Attempt to match from seventh character in Text Text: tantatsi Pattern: t does not match ----------------------------------------------- Attempt to match from eighth character in Text Text: tantatsi Pattern: t does not match, end of textNotice that the position of the pattern is advanced by one letter in the text if there is a mismatch and by the length of the pattern if there was a match.
As shown in the next example, this difference in behavior is because we do not allow overlapping matches:
Suppose our text is hihih and the pattern is hih:
Attempt to match from first character in Text Text: hihih Pattern: h matches hi matches hih matches, end of pattern ---------------------------------------------- Attempt to match from fourth character in Text Text: hihih Pattern: h does not match ---------------------------------------------- Attempt to match from fifth character in Text Text: hihih Pattern: h matches, end of textWe only want the first hih to count as a match.