So we define LCP array and let's consider suffix array A of string S in the raw form that is that A[0] is a suffix, A[1] is a suffix and so on up to A[S-1], all those are suffixes of S in lexicographic order. Then LCP array of string S is the array LCP small of size length of S-1. It contains fewer elements than the suffix array and then the string itself. Besides that, each element lcp[i] is just equal to the longest common prefix length. Between A[i] and A[i+1]. So it's the longest common prefix of two neighboring elements in the suffix array and what we want is to compute the values of this array. For example if we have our string ababaa$. Then, we first compute the longest common prefix of $, and a$, which is 0. Then, we compute the longest common prefix of a$ and aa$, which is a of length 1. Then it's again a of length 1. Then it's aba of length 3. Then it's empty. And then it's ba of length 2. so the LCP array for this string is 0, 1,1, 3, 0, 2. And the central LCP array property which will enable us to compute it fast is that for any end assist i and j In the suffix array, where i is less than j. The longest common prefix between A[i] and A[j] which are far from each other, is not bigger than the LCP of i, which is basically the longest common prefix of i and the next element. So what I'm saying with this Lemma is that the LCP of two neighboring elements is always at least as big as the LCP of the first one of them with any of the next elements. And the same goes the other way. The LCP of two neighboring elements is at least the same as LCP of the second of them with any of the previous ones. And to see that let's look at some hypothetical example that we have some long suffix array and elements i and i+1 are here. And also there is some element j farther in the suffix array. And we see that really the common prefix of suffixes i and i+1 is pretty long. It's not so long with suffix j, it's only of length two. But this example doesn't yet prove anything. So maybe for some other situation with a suffix number i+1, it could be solved that the common prefix of i and j will be bigger than common prefix of i and i+1. So let's suppose that, and we don't know what is suffix i + 1, so we just replace it with many x. X is an unknown letter. We know that the LCP of i and j is equal to 2. So let's consider k which is the length of the longest common prefix of A[i] and A[i + 1]. And we suppose that it is smaller than 2 in this case. So how can that be? One variant is if A[i + 1] is shorter than 2, and then A[i + 1] is actually a prefix of A[i]. But in this case, A[i+1] is smaller than Ai which contradicts the property of the suffix array. That the suffixes are sorted. And if suffix i+1 is sufficiently long then it follows that it's kth character is different from the kth character of both ith suffix and jth suffix. And in this case there are again two cases. In the first case is that this character in suffix i+1 is bigger than the corresponding one in strings i and j. But from this it immediately follows that suffix i+1 is bigger than suffix j which contradicts the suffix array properties, so it is impossible. And another case is that this character is less than the corresponding character in both strings i and j. But in this case it immediately follows that A[i] is bigger than A[i + 1] which again contradicts the suffix array property. So in all cases we found the contradiction. And so, it is not possible that the longest common prefix of i and j is bigger than the longest common prefix of i and i+1. And we proved the LCP array property because for this symmetric case, the proof is a null x. Now how do we compute the LCP array? One variant is to go for each i, compare A[i] and A[i+1] character by character and compute the LCP directly. But this will work in linear time for each i. And in total it will be length of the string squared. And we want to compute everything in linear time. So how to do this faster, and you will learn that in the next video.