What is an LCP array?

The longest common prefix (LCP) array supplements the suffix array by storing the lengths of the longest common prefixes between pairs of adjacent suffixes in the suffix array. It is usually used with a suffix array to speed up pattern matching.

A suffix is a collection of characters at the end of a string. A suffix array contains array indices of the first letters of all the non-empty suffixes of a string sorted in alphabetical order. The suffix array for the ​string “papaya” is created as follows:

The following illustration shows how the LCP array is created from the suffix array: