Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structures

What is an LCP array?

Educative Answers Team

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:

A table containing all non-empty suffixes and the indices of their first letter.
1 of 3

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

The suffix array of "papaya".
1 of 9


data structures
Copyright ©2022 Educative, Inc. All rights reserved

View all Courses

Keep Exploring