+/*
+ * Build the LCP (Longest Common Prefix) array in linear time.
+ *
+ * LCP[r] will be the length of the longest common prefix between the suffixes
+ * with positions SA[r - 1] and SA[r]. LCP[0] will be undefined.
+ *
+ * Algorithm taken from Kasai et al. (2001), but modified slightly:
+ *
+ * - For decreased memory usage and improved memory locality, pack the two
+ * logically distinct SA and LCP arrays into a single array SA_and_LCP.
+ *
+ * - With bytes there is no realistic way to reserve a unique symbol for
+ * end-of-buffer, so use explicit checks for end-of-buffer.
+ *
+ * - If a LCP value is less than the minimum match length, then store 0. This
+ * avoids having to do comparisons against the minimum match length later.
+ *
+ * - If a LCP value is greater than the "nice match length", then store the
+ * "nice match length". This caps the number of bits needed to store each
+ * LCP value, and this caps the depth of the LCP-interval tree, without
+ * usually hurting the compression ratio too much.
+ *
+ * References:
+ *
+ * Kasai et al. 2001. Linear-Time Longest-Common-Prefix Computation in
+ * Suffix Arrays and Its Applications. CPM '01 Proceedings of the 12th
+ * Annual Symposium on Combinatorial Pattern Matching pp. 181-192.
+ */
+static void
+build_LCP_packed(u32 * const restrict SA_and_LCP, const u32 * const restrict ISA,
+ const u8 * const restrict T, const u32 n,
+ const u32 min_lcp, const u32 max_lcp)
+{
+ u32 h, i, r, j, lim, stored_lcp;
+
+ h = 0;
+ for (i = 0; i < n; i++) {
+ r = ISA[i];
+ if (r > 0) {
+ j = SA_and_LCP[r - 1] & SA_and_LCP_POS_MASK;
+ lim = min(n - i, n - j);
+ while (h < lim && T[i + h] == T[j + h])
+ h++;
+ stored_lcp = h;
+ if (stored_lcp < min_lcp)
+ stored_lcp = 0;
+ else if (stored_lcp > max_lcp)
+ stored_lcp = max_lcp;
+ SA_and_LCP[r] |= stored_lcp << SA_and_LCP_LCP_SHIFT;
+ if (h > 0)
+ h--;
+ }
+ }
+}
+