### PROBLEM LINK

### DIFFICULTY

MEDIUM

### PREREQUISITES

### PROBLEM

You are given a sequence of **heights**. You wish to find the number of unique contiguous subsequences in **heights**, such that, for any two of them

- Either their
**length**is different - The sequences formed by taking
**difference between consecutive heights**, is different

### QUICK EXPLANATION

We can take the **difference between consecutive heights** and work on only those. We wish to find the number of **unique contiguous subsequences** (we consider that two subsequences are different anyway if they have different lengths).

This is equivalent to the problem of finding the **number of unique substrings in a string**. For the rest of this discussion, we will refer to the length of the string as **N**.

The naive method to finding the number of unique substrings in a string is to consider each sub-string and find the number of unique ones. This algorithm can be implemented in **O(N ^{2})** by using a smart hash function and a hash table.

Another **O(N ^{2})** approach uses the Knuth Morris Pratt algorithm. The

**failure function**may be calculated for each

**suffix**of the string and used to eliminate

**repeated**substrings. We will not discusss this approach in detail because in this problem the length of the string can be as much as

**99,999**. This means that we cannot use any

**O(N**approach.

^{2})You may already know about the **Suffix Arrays** and **LCP Arrays**. We can use them to solve this problem in **O(N)**. Refer to the this paper to learn the **Skew Algorithm** for sorting suffixes and finding **LCP Array** in **O(N)** time.

We will describe an algorithm to construct the Suffix Array in order **O(Nlog ^{2}N)** and then find the

**Longest Common Prefixes**between adjacent suffixes in the Suffix Array in

**O(log N)**time. The explanation below is largely based on this resource.

We will then see how to find the number of unique substrings of a string by using the **LCP Array**.

### EXPLANATION

Take the example of the following string

mississippi length = 11

The suffixes of the above string are

0: mississippi 1: ississippi 2: ssissippi 3: sissippi 4: issippi 5: ssippi 6: sippi 7: ippi 8: ppi 9: pi 10: i

If we were to sort all the above suffixes in lexicographic order, we would obtain the string

10: i 7: ippi 4: issippi 1: ississippi 0: mississippi 9: pi 8: ppi 6: sippi 3: sissippi 5: ssippi 2: ssissippi

Whenever we say Suffix Array, we mean the integer array representing the order in which the suffixes appear when sorted.

[ 10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2 ]

A naive way in which you can create the above array is to start with the array

[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

And then apply the standard **quick-sort** algorithm using a **comparator function** that compares two strings. The complexity of sorting the array and obtaining the Suffix Array would be **O(N ^{2}log N)**.

But surely we can do better. We know that we are not sorting random strings, rather, strings that are suffixes of the same string.

Let us consider the original array or suffixes, **sorted only according to the first 2 character**. If the first 2 character is the same, we consider that the strings have the same **sort index**.

Sort-Index Suffix-Index 0 10:i1 7:ippi 2 1:ississippi 2 4:issippi 3 0:mississippi 4 9:pi5 8:ppi 6 3:sissippi 6 6:sippi 7 2:ssissippi 7 5:ssippi

Now, we wish to use the above array, and **sort the suffixes according to their first 4 characters**. To achieve this, we can assign **2-tuples** to each string. The first value in the **2-tuple** is the **sort-index** of the respective suffix, from above. The second value in the **2-tuple** is the **sort-index** of the suffix that starts **2 positions later**, again from above.

If the length of the suffix is less than 2 characters, then we can keep the second value in the **2-tuple** as **-1**.

Sort-Index Suffix-Index Suffix-Index after first 2 chars and 2-tuple assigned 0 10:i-1 (0, -1) 1 7:ippi 9 (1, 4) 2 1:ississippi 3 (2, 6) 2 4:issippi 6 (2, 6) 3 0:mississippi 2 (3, 7) 4 9:pi-1 (4, -1) 5 8:ppi 10 (5, 0) 6 3:sissippi 5 (6, 7) 6 6:sippi 8 (6, 5) 7 2:ssissippi 4 (7, 2) 7 5:ssippi 7 (7, 1)

Now, we can call **quick-sort** and sort the suffixes according to their first 4 characters by using the **2-tuples** we constructed above! The result would be

Sort-Index Suffix-Index 0 10:i1 7:ippi2 1:ississippi 2 4:issippi 3 0:mississippi 4 9:pi5 8:ppi6 3:sissippi 7 6:sippi 8 2:ssissippi 9 5:ssippi

Similarly constructing the **2-tuples** and performing **quick-sort** again will give us suffixes sorted by their **first 8 characters**.

Thus, we can sort the suffixes by the following pseudo-code

SortIndex[][] = { 0 } for i = 0 to N-1 SortIndex[0][i] = order index of the character at A[i] doneTill = 1 step = 1 while doneTill < N L[] = { (0,0,0) } // Array of 3 tuples for i = 0 to N-1 L[i] = ( SortIndex[step - 1][i], SortIndex[step - 1][i + doneTill], i ) // We need to store the value of i to be able to retrieve the index sort L for i = 0 to N-1 SortIndex[step][L[i].thirdValue] = 0, if L[i] and L[i-1] have the same first and second values i, otherwise ++step doneTill *= 2

The above algorithm will find the Suffix Array in **O(N log ^{2} N)**. This is, in fact, enough for this problem.

We can use the **SortIndex** array we constructed above to find the **Longest Common Prefix**, between any two prefixes.

FindLCP (x, y) answer = 0 for k = ceil(log N) to 0 if SortIndex[k][x] = SortIndex[k][y] // sort-index is same if the first k characters are same answer += 2^{k}// now we wish to find the characters that are same in the remaining strings x += 2^{k}y += 2^{k}

The **LCP Array** is the array of **Longest Common Prefixes** between the **i ^{th}** suffix and the

**(i-1)**suffix in the Suffix Array. The above algorithm needs to be called

^{th}**N**times to build the

**LCP Array**in a total of

**O(N log N)**time.

The **LCP Array** for the string we have been using till now is

LCP SA 0 10: i 1 7:ippi 1 4:issippi 4 1:ississippi 0 0: mississippi 0 9: pi 1 8:ppi 0 6: sippi 2 3:sissippi 1 5:ssippi 3 2:ssissippi

Once we know the LCP array, we can find the number of unique substrings by **simply ignoring all the prefixes of each suffix that were common from the suffix before it - since they were already counted as the prefix of the last suffix**. Hence the answer is

(Sum of length of all Suffixes) - (Sum of values in LCP Array)

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.