Any one knows who is the inventor of the Z-algorithm??!!
Any one knows who is the inventor of the Z-algorithm??!!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
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?
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
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.