Building a Suffix Array in JavaScript

A suffix array is a fundamental data structure in string processing, enabling efficient solutions to a variety of problems like pattern searching, longest common substring, and distinct substring counting. This challenge asks you to implement a function that constructs a suffix array for a given input string in JavaScript.

Problem Description

Your task is to create a JavaScript function createSuffixArray(text) that takes a string text as input and returns its suffix array.

A suffix array for a string $T$ is an array of integers representing the starting positions of all suffixes of $T$ after they have been lexicographically sorted.

For example, if the input string is "banana": The suffixes are:

• "banana" (starts at index 0)
• "anana" (starts at index 1)
• "nana" (starts at index 2)
• "ana" (starts at index 3)
• "na" (starts at index 4)
• "a" (starts at index 5)

When sorted lexicographically, these become:

• "a" (starts at index 5)
• "ana" (starts at index 3)
• "anana" (starts at index 1)
• "banana" (starts at index 0)
• "na" (starts at index 4)
• "nana" (starts at index 2)

Therefore, the suffix array would be [5, 3, 1, 0, 4, 2].

Examples

Example 1:

Input: "banana"
Output: [5, 3, 1, 0, 4, 2]
Explanation: As described above, the sorted starting indices of the suffixes of "banana".

Example 2:

Input: "abracadabra"
Output: [10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2]
Explanation: The sorted starting indices of the suffixes of "abracadabra".

Example 3:

Input: "aaaaa"
Output: [4, 3, 2, 1, 0]
Explanation: All suffixes are identical prefixes of each other. Their lexicographical order depends on their starting positions when they are identical.

Constraints

• The input text will be a string consisting of lowercase English letters (a-z).
• The length of text will be between 1 and 1000, inclusive.
• The output should be an array of integers.
• The algorithm should aim for reasonable performance. While brute-force sorting of all suffixes might pass for small inputs, consider if a more optimized approach could be necessary for larger inputs within a typical competitive programming context.

Notes

You can approach this problem by generating all suffixes and then sorting them. However, be mindful of the efficiency of string comparisons and sorting. For more advanced implementations, algorithms like the Skew algorithm or SA-IS algorithm are significantly more performant, but for this challenge, a straightforward approach is acceptable. Remember that in JavaScript, strings are immutable, and slicing a string creates a new string.