Practice problems on Suffix Array
- Check if given words are present in a string
- Counting k-mers via Suffix Array
- Count of distinct substrings of a string using Suffix Array
- Print Kth character in sorted concatenated substrings of a string
- Construct array B as last element left of every suffix array obtained by performing given operations on every suffix of given array
Suffix Arrays for Competitive Programming
A suffix array is a sorted array of all suffixes of a given string. More formally if you are given a string ‘S’ then the suffix array for this string contains the indices 0 to n, such that the suffixes starting from these indices are sorted lexicographically.
Example:
Input: banana
0 banana 5 a
1 anana Sort the Suffixes 3 ana
2 nana —————-> 1 anana
3 ana alphabetically 0 banana
4 na 4 na
5 a 2 nanaSo the suffix array for “banana” is {5, 3, 1, 0, 4, 2}
Contact Us