Блог пользователя Safrout

Z-algorithm inventor
Автор Safrout, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить