Hi guys,
I am familiar with the Z algorithm for exact string matching.
However, is there a way to do this without using the sentinel
which is commonly #?
An idea i have is if m is the length of the pattern and n the length of the text, then we can do this
let S = P+T compute Z table
since the pattern is of length n, start iterating from i = m to i = n+m-1 if Z[i] >= m then we have a match at i. Is this correct?
That's correct. The only difference is that Z values for P#T are bounded by |P|, whereas for PT they are bounded by |PT|. It matters if either P is small enough to store Z values in a few bits, or T is an infinite stream, for example.