Suffix Array

This page provides links to solutions that use the Suffix Array data structure.

Overview

A suffix array contains integers that represent the starting indices of the suffixes of a given string, after the suffixes have been sorted.

Let's take an example for a string $\text{s = abaab}$ . All suffixes of given string will be as follows:

• $\text{abaab}$ - $0^{\text{th}}$ index
• $\text{baab}$ - $1^{\text{st}}$ index
• $\text{aab}$ - $2^{\text{nd}}$ index
• $\text{ab}$ - $3^{\text{rd}}$ index
• $\text{b}$ - $4^{\text{th}}$ index

After sorting these strings we get:

• $\text{aab}$ - $2^{\text{nd}}$ index
• $\text{ab}$ - $3^{\text{rd}}$ index
• $\text{abaab}$ - $0^{\text{th}}$ index
• $\text{b}$ - $4^{\text{th}}$ index
• $\text{baab}$ - $1^{\text{st}}$ index

Therefore the suffix array for string $\text{s}$ will be: $[2, 3, 0, 4, 1]$.

Build Suffix Array

Let's create suffix array for input string $\text{s=banana}$. All the suffixes of input string will be as below:

• $\text{banana}$
• $\text{anana}$
• $\text{nana}$
• $\text{ana}$
• $\text{na}$
• $\text{a}$

To generate the suffix array, we will begin by defining a suffix class that implements the comparable interface to compare two suffixes, as shown below:

Java

// Suffix class to store the originalIndex, rank, and nextRank of a suffix
private static class Suffix implements Comparable<Suffix> {
  int originalIndex;
  int rank;
  int nextRank;

  // Constructor to initialize the originalIndex, rank, and nextRank
  Suffix(int originalIndex, int rank, int nextRank) {
    this.originalIndex = originalIndex;
    this.rank = rank;
    this.nextRank = nextRank;
  }

  // Compare two suffixes
  @Override
  public int compareTo(Suffix other) {
    int c = Integer.compare(this.rank, other.rank);
    return c == 0 ? Integer.compare(this.nextRank, other.nextRank): c;
  }
}

Let's create a suffix object for each suffixes as below:

suffix	original_index	rank	next_rank
$\text{banana}$	$0$	$1$	$0$
$\text{anana}$	$1$	$0$	$13$
$\text{nana}$	$2$	$13$	$0$
$\text{ana}$	$3$	$0$	$13$
$\text{na}$	$4$	$13$	$0$
$\text{a}$	$5$	$0$	$-1$

info

The original index in the suffix object above represents the position of the suffix in the string $\text{s}$. For example suffix $\text{banana}$ starts at index $0$ in a string.

Rank and next rank represents ranks of first and second character of suffix in english alphbets. For example if character is "a" rank will be $0$, if character is "b" rank will be $1$, if character is "c" rank will be $2$ and so on.

Once suffix objects are ready, sort them by rank first and then by next rank as below:

suffix	original_index	rank	next_rank
$\text{a}$	$5$	$0$	$-1$
$\text{anana}$	$1$	$0$	$13$
$\text{ana}$	$3$	$0$	$13$
$\text{banana}$	$0$	$1$	$0$
$\text{nana}$	$2$	$13$	$0$
$\text{na}$	$4$	$13$	$0$

Now, our goal is to group suffixes that have the same first two characters together, by assigning them same rank.

For example, in suffix object table above, suffix $\text{a}$ and next suffix $\text{anana}$ do not have the same first two characters, so we will assign different rank to them, whereas suffix $\text{anana}$ and next suffix $\text{ana}$ do have same first two characters, so we will assign same rank to them. And so on.

The logic for reassigning rank will be as below:

Java

// first suffix will be given a rank of 0.
int rank = 0;

// previousRank variable is used here because we override existing rank of each suffix.
int previousRank = suffixes[0].rank;

// overriding rank of 0th suffix.
suffixes[0].rank = rank;

// idxMapping stores mapping of suffix's original index to next index.
idxMapping[suffixes[0].originalIndex] = 0;

for (int i = 1; i < n; i++) {
  // compare rank and next rank of current and previous suffix.
  if (previousRank != suffixes[i].rank || suffixes[i - 1].nextRank != suffixes[i].nextRank) {
    // if rank is not same
    // store current suffix's old rank as previous rank and 
    // increment rank
    previousRank = suffixes[i].rank;
    rank++;
  }

  // override rank of current suffix
  suffixes[i].rank = rank;

  // store mapping of current suffix's original index to new index
  idxMapping[suffixes[i].originalIndex] = i;
}

For readability, I have retained old rank and old next_rank values in suffix object table. After overriding rank for each suffix, our suffix objects will looks like below:

suffix	original_index	old_rank	old_next_rank	rank	next_rank	idx_mapping
$\text{a}$	$5$	$0$	$-1$	$\textbf{0}$	$-1$	$\textbf{3}$
$\text{anana}$	$1$	$0$	$13$	$\textbf{1}$	$13$	$\textbf{1}$
$\text{ana}$	$3$	$0$	$13$	$\textbf{1}$	$13$	$\textbf{4}$
$\text{banana}$	$0$	$1$	$0$	$\textbf{2}$	$0$	$\textbf{2}$
$\text{nana}$	$2$	$13$	$0$	$\textbf{3}$	$0$	$\textbf{5}$
$\text{na}$	$4$	$13$	$0$	$\textbf{3}$	$0$	$\textbf{0}$

info

In above table, idx_mapping indicates current index of each suffix given original index. For example, idx_mapping[5] = 0 indicates suffix $\text{a}$ which was at index $5$ in original string $\text{banana}$ is now at $0^\text{th}$ index.

Up until now we have compared first $2$ characters of each suffix using rank and next rank. Now, we will compare next two characters of each suffix and to achieve this we override next rank for each suffix.

To calculate next rank we add $2$ to suffix's original index and retrieve the rank of the suffix that was originally at that index.

For example, first suffix $\text{a}$ have original index of $5$, adding $2$ to it gives us $7$, which is out of bounds for given string $\text{banana}$, so we assign next rank as $-1$.

Similarly, second suffix $\text{anana}$ have original index of $1$, adding $2$ to it gives us $3$. Originally suffix $\text{ana}$ was at index $3$ in given string $\text{banana}$, so we retrieve rank of suffix $\text{ana}$ which is $1$ and assign it to suffix $\text{anana}$.

The logic for reassinging next rank will be as below:

Java

for (int i = 0; i < n; i++) {
  // k here will be multiples of 2
  int nextIndex = suffixes[i].originalIndex + k;
  // new index of suffix array which was original at nextIndex
  int newIndex = idxMapping[nextIndex];
  // assign next rank
  suffixes[i].nextRank = (nextIndex < n) ? suffixes[newIndex].rank : -1;
}

After reassigning next rank for each suffix, our suffix objects will look like below:

suffix	original_index	old_rank	old_next_rank	rank	next_rank	idx_mapping
$\text{a}$	$5$	$0$	$-1$	$0$	$\textbf{-1}$	$3$
$\text{anana}$	$1$	$1$	$13$	$1$	$\textbf{1}$	$1$
$\text{ana}$	$3$	$1$	$13$	$1$	$\textbf{0}$	$4$
$\text{banana}$	$0$	$2$	$0$	$2$	$\textbf{3}$	$2$
$\text{nana}$	$2$	$3$	$0$	$3$	$\textbf{3}$	$5$
$\text{na}$	$4$	$3$	$0$	$3$	$\textbf{-1}$	$0$

Now, that we have reassigned rank and next rank, we sort the suffixes again. After sorting again, suffixes will look like below:

suffix	original_index	rank	next_rank	idx_mapping
$\text{a}$	$5$	$0$	$-1$	$3$
$\text{ana}$	$3$	$1$	$0$	$4$
$\text{anana}$	$1$	$1$	$1$	$1$
$\text{banana}$	$0$	$2$	$3$	$2$
$\text{na}$	$4$	$3$	$-1$	$0$
$\text{nana}$	$2$	$3$	$3$	$5$

info

Upto this point suffixes are sorted by first $4$ characters, in the next iteration we will consider first $8$ characters. To achive that we calculate next rank by adding $4$ to current suffix's original index.

Firstly, we will repeat the process of reassigning the rank for each suffix. After reassigning rank our suffixes objects will look like below:

suffix	original_index	old_rank	old_new_rank	rank	next_rank	idx_mapping
$\text{a}$	$5$	$0$	$-1$	$\textbf{0}$	$-1$	$\textbf{3}$
$\text{ana}$	$3$	$1$	$0$	$\textbf{1}$	$0$	$\textbf{2}$
$\text{anana}$	$1$	$1$	$1$	$\textbf{2}$	$1$	$\textbf{5}$
$\text{banana}$	$0$	$2$	$3$	$\textbf{3}$	$3$	$\textbf{1}$
$\text{na}$	$4$	$3$	$-1$	$\textbf{4}$	$-1$	$\textbf{4}$
$\text{nana}$	$2$	$3$	$3$	$\textbf{5}$	$3$	$\textbf{0}$

Next we will repeat process of reassigning the next rank for each suffix. After reassigning next rank our suffix objects will look like below:

suffix	original_index	old_rank	old_new_rank	rank	next_rank	idx_mapping
$\text{a}$	$5$	$0$	$-1$	$0$	$\textbf{-1}$	$3$
$\text{ana}$	$3$	$1$	$0$	$1$	$\textbf{-1}$	$2$
$\text{anana}$	$1$	$1$	$1$	$2$	$\textbf{0}$	$5$
$\text{banana}$	$0$	$2$	$3$	$3$	$\textbf{4}$	$1$
$\text{na}$	$4$	$3$	$-1$	$4$	$\textbf{-1}$	$4$
$\text{nana}$	$2$	$3$	$3$	$5$	$\textbf{-1}$	$0$

Finally, we sort suffix objects as below:

suffix_array_index	suffix	original_index	rank	next_rank	idx_mapping
$0$	$\text{a}$	$5$	$0$	$-1$	$3$
$1$	$\text{ana}$	$3$	$1$	$-1$	$2$
$2$	$\text{anana}$	$1$	$2$	$0$	$5$
$3$	$\text{banana}$	$0$	$3$	$4$	$1$
$4$	$\text{na}$	$4$	$4$	$-1$	$4$
$5$	$\text{nana}$	$2$	$5$	$-1$	$0$

At this point, the suffixes are sorted by the first $8$ characters and can be considered fully sorted because none of the suffixes has a length greater than $8$.

Now, to get the suffix array we just retrieve original index for each suffix and get suffix array as below:

$$[5, 3, 1, 0, 4, 2]$$

Java

// function to construct the suffix array
public static int[] buildSuffixArray(char[] s) {
  int n = s.length;
  Suffix[] suffixes = new Suffix[n];

  // Step 1: Create a Suffix object for each character in the input array
  for (int i = 0; i < n; i++) {
    suffixes[i] = new Suffix(
      i, // original index
      s[i] - 'a',  // rank
      (i + 1 < n) ? s[i + 1] - 'a' : -1 // next rank
    );
  }

  // Step 2: Sort the suffixes based on rank and next rank using a custom comparator
  Arrays.sort(suffixes);

  // An array to store the suffix indices in their sorted order
  int[] idxMapping = new int[n];

  // Step 3: Assign ranks and create the suffix index array
  for (int k = 2; k <= n; k *= 2) {
    int rank = 0;
    int previousRank = suffixes[0].rank;
    suffixes[0].rank = rank;
    idxMapping[suffixes[0].originalIndex] = 0;

    // Step 3.1: Assign ranks based on suffix comparisons
    for (int i = 1; i < n; i++) {
      if (previousRank != suffixes[i].rank || suffixes[i - 1].nextRank != suffixes[i].nextRank) {
        previousRank = suffixes[i].rank;
        rank++;
      }
      suffixes[i].rank = rank;
      idxMapping[suffixes[i].originalIndex] = i;
    }

    // Step 3.2: Assign nextRank for each suffix
    for (int i = 0; i < n; i++) {
      int nextIndex = suffixes[i].originalIndex + k;
      suffixes[i].nextRank = (nextIndex < n) ? suffixes[idxMapping[nextIndex]].rank : -1;
    }

    // Step 3.3: Sort the suffixes based on rank and next rank using the custom comparator
    Arrays.sort(suffixes);
  }

  // Step 4: Create the final suffix array and return it
  int[] result = new int[n];
  for (int i = 0; i < n; i++) {
    result[i] = suffixes[i].originalIndex;
  }
  return result;
}

Complexity

Let's say there are $\text{N}$ characters in an input string.

Time Complexity

• Assigning ranks takes $\text{O(N)}$ time.
• Sorting ranks of $\text{N}$ suffixes takes $\text{O(N log N)}$ time.
• These steps are repeated $\text{O(log N)}$ times.

So total time complexity to build suffix array will be:

$$\text{O}(\text{N log}^{2} \text{N})$$

info

Time complexity to build suffix array can be reduced to $\text{O}(\text{N log } \text{N})$ by using radix sort for sorting ranks.

Space Complexity

Algorithm uses linear space for storing ranks, so space complexit to build suffix array will be:

$$\text{O(N)}$$

How to Spot These Problems

You can identify Suffix Array problems if the problem requires you to:

• Find the longest or shortest suffix, prefix, or substring.

Leetcode Problem Set