Fig. 2
From: Fast, parallel, and cache-friendly suffix array construction
Figure illustrating the cases that can occur on the \((k+1)\)’th step of the merge routine, which determines \(Z_{k+1}\). Cases 1 and 2 require \(\mathcal {O}(1)\) work and simply compare the LCP-lengths of the previous step and \({\textsc {LCP}}{}(X_{i+1}, X_{i})\), which are already available. Step 3 requires work proportional to \(\mathcal {O}({\textsc {LCP}}(X_{i+1}, Y_{j}) - m)\), since \(X_{i+1}, Y_{j}\) already share a prefix of size \(m\)