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(N2) by using a smart hash function and a hash table.
Another O(N2) 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(N2) approach.
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(Nlog2N) 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(N2log 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: i
1 7: ippi
2 1: ississippi
2 4: issippi
3 0: mississippi
4 9: pi
5 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: i
1 7: ippi
2 1: ississippi
2 4: issippi
3 0: mississippi
4 9: pi
5 8: ppi
6 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 log2 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 += 2k
// now we wish to find the characters that are same in the remaining strings
x += 2k
y += 2k
The LCP Array is the array of Longest Common Prefixes between the ith suffix and the (i-1)th suffix in the Suffix Array. The above algorithm needs to be called 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.
One small request i have few doubt on