Some errors in the linear time LCP paper
Section 3 in the paper
Linear-Time
Longest-Common-Prefix Computation in Suffix Arrays and Its
Applications.. Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo
Arikawa, Kunsoo Park. Proceedings of Combinatorial Pattern Matching (CPM),
Springer, 2001, pages 181-192.
seems to contain the following errors/typos in Section 3:
- On page 185, ">1" should be ">=1" in Fact 2, Fact 3, Lemma 3, and
Theorem 1.
- On page 185, in proof of Lemma 3, "Since" should be "Hence", and
"we get" should be "so we get".
- On page 186, in line 8 of the code, "j" should be "k".
- On page 186, the code does not deal with the effect on correctness
of skipping the case "Rank[i] > 1" (which is correct to do). Theorem 1 does
not seem to be applicable in the next iteration after the skip. A simple
fix is to reset h to zero during the skipping (add an else clause to the
if), which clearly makes the algorithm correct (since now it maintains the
invariant that h before each iteration is a lower bound on lcp to be found
in the iteration) and only adds n to the time analysis (the skip only
happens once, and "sets back" h by at most n).
Maintained by Rolf Fagerberg
(rolf@imada.sdu.dk)
|
|