LCParray

LCParray, or the LCP array, is a data structure used in string processing. It records, for each adjacent pair of suffixes in the suffix array of a string S, the length of the longest common prefix between those two suffixes. Formally, for a string S of length n and SA[0..n-1] as the suffix array, the LCP array LCP[0..n-1] is defined by LCP[i] = LCP(S[SA[i]..], S[SA[i-1]..]) for i > 0, and LCP[0] = 0.

Construction and properties: Given S and its SA, the LCP array can be computed in O(n) time using Kasai’s algorithm. Many suffix array constructions produce both SA and LCP as part of the process. LCP values are nonnegative and bounded by n − SA[i], the remaining length of the suffix.

Queries and RMQ: The LCP array enables rapid LCP queries between arbitrary suffixes via a range minimum query on the interval between their positions in SA. If p and q are starting positions, with pos[p] and pos[q] their ranks in SA, then LCP(S[p..], S[q..]) = min{ LCP[k] : k lies between min(pos[p], pos[q]) + 1 and max(pos[p], pos[q]) }.

Applications: LCP arrays underpin efficient pattern matching, substring search, counting distinct substrings, data compression schemes, and the construction of suffix trees or improved suffix arrays. They also support bioinformatics tasks involving genome substring queries.

Example: For the string "banana", the suffix array is SA = [5, 3, 1, 0, 4, 2], and the LCP array is LCP = [0, 1, 3, 0, 0, 2]. This reflects the common prefix lengths between adjacent suffixes in that order.