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)