Answer to Question 3
Practice Questions for Exam 6

Imagine trying the pattern starting at a particular index i in the text t. When a character of the pattern does not match t_i, the prefix function tells how far to move the pattern ahead to the next possible match. It also guarantees that, at the new location, the pattern matches all text characters at indices less than i that still overlap the pattern, so that they don't need to be rechecked.

For example, suppose pattern ababd is being tried as follows.

  t = cabbccababcabababc
  p =       ababd

The first 4 characters of the pattern match the text at this location, but the fifth character is a mismatch. The prefix function says to slide the pattern ahead 2 spots, as follows.

  t = cabbccababcabababc
  p =         ababd

The first two characters, ab, do not need to be checked. Instead, we continue by testing whether the third character of the pattern matches c in the text.