Proof:
Construct the suffix array \(SA[1\ldots n]\)  and \(LCP\) -Array \(LA[1\ldots n]\) , where \(LA(i)=LCP(SA[i-1],SA[i])\) , in \(O(n)\)  time  [1]}, [2]}. We set \(r(1) = 0\)  and proceed to set \(r(i)\)  for \(i \in [2 \ldots n]\)  in increasing order of \(i\) .
