Safrout's blog

Z-algorithm inventor
By Safrout, 9 years ago, In English

Any one knows who is the inventor of the Z-algorithm??!!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe Dan Gusfield is the inventor. My professor for a computational biology class I took made this claim but I can't find any source on the internet to back it up!

Z-values is discussed in his book "Algorithms on Strings, Trees, and Sequences". I don't own this book but he may make the claim to inventing the algorithm in the first chapter? If someone owns the book, can they confirm this?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The book is actually in my university's library

    The German University in Cairo.

    I do read it often but I didn't observe that he is the inventor.

    I will double check the book. Thank you

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that the idea of the linear-time preprocessing was first described in the paper "An O(n log n) algorithm for finding all repetitions in a string" by Main and Lorentz (1984).

Then, in 1994 Gusfield published the tech report "Simple Uniform Preprocessing for Linear-time Pattern Matching" in which he shows that the preprocessing can be used by multiple linear-time string matching algorithms. Gusfield cites Main and Lorentz as the original authors of the preprocessing.

→ Reply