binary_eagle's blog

Help with Z algorithm without sentinel
By binary_eagle, history, 8 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply