A suffix array is a sorted list of all the suffixes in a string. Consider the string “ball”, its suffixes are as follows:

• ball (suffix starting from index 0)
• all (suffix starting from index 1)
• ll (index 2)
• l (index 3)

After sorting it in lexicographical order, we will get the suffix array, i.e.,

• all (index 1)
• ball (index 0 )
• l (index 3)
• ll (index 2)

First approach

But how do we write a program that can do this for us? One straightforward approach is to generate all the suffixes first and then sort them. It is quite simple to code. However, it is not efficient. Its time complexity is O(n2logn), i.e., O(n) to generate the suffixes and O(nlogn) to sort them, where n is the length of the string.  

def naiveSuffixArray(str):
  sa = [] #suffix array
  n = len(str) #length of array
  #generate suffixes
  for i in range(0, n):
    sa.append(str[i:n])
  #sorting them
  sa = sorted(sa)
  return sa

str = "banana"
SA = naiveSuffixArray(str)
print(SA)

[‘a’, ‘ana’, ‘anana’, ‘banana’, ‘na’, ‘nana’]

A better and faster approach

Let’s now talk about a better approach with O’s time complexity (n(logn)2). This approach works by sorting the first K occurrences in suffixes, where K is a power of 2 and less than 2×n. For example, it sorts the suffixes based on the first two characters, then four, etc. It does that by keep ranks and next ranks of the suffixes.

To better understand how this algorithm works, let’s apply it on the string “ball” to generate its suffix array.

First, sort the suffixes according to the first two characters by assigning rank and next rank to each suffix. Usually, the rank is obtained using str[i]-"a", where str[i] denotes the starting character of each suffix. The next rank is equal to str[i+1]-"a", where str[i+1] is the second character in the suffix. If it does not exist, the next rank becomes -1.

After sorting it by the rank and next rank, we get:

Now let’s sort the suffixes according to the first four characters. Here, the ranks and next ranks get reassigned. To do that, assign 0 to the rank of the first suffix in the list, then Iterate through the remaining suffixes and check if the rank and the next rank of the previous suffix and the current suffix are equal. If they are, assign the same rank to the current suffix as the previous one. Otherwise, increment the previous rank by 1.

For the next rank’s value, extract the suffix from the i+2 position, where i is the first character in the suffix. Find that suffix in the list and place its rank value as the next rank of the current suffix. If i+1 is out of range, then set -1 as the next rank.

As you can observe, the list won’t change after sorting, and since we have considered all the characters, the above-given list is the resulting suffix array.

Implementation

def suffixArray(str):
  n = len(str) 
  #sorting by first two characters
  #get the index, rank and next rank for each suffix
  suffixes = [ {"index":i, "rank": ord(str[i])-ord('a'), "next_rank":  (ord(str[i+1])-ord('a')) if (i!=n-1) else -1 } for i in range(0, n)] #array of dictionary

  #sort the suffixes
  suffixes = sorted(suffixes, key = lambda i: (i['rank'], i['next_rank']))
  #create an array to keep track of indices of the suffixes array
  index = [0]*n
  #sort for k=4, 8, ... characters
  k=4
  while k<(2*n):
    rank=0 #rank 0 to the suffix 0
    prev_rank = suffixes[0]['rank'] #saving the pervious rank of the first suffix
    suffixes[0]['rank']  = rank  
    #assigning new ranks to suffixes
    for i  in range(1, n):
      if (suffixes[i]['rank']==prev_rank and suffixes[i]['next_rank']==suffixes[i-1]['next_rank']):
        prev_rank = suffixes[i]['rank']
        suffixes[i]['rank'] = rank
      else:
        prev_rank = suffixes[i]['rank']
        rank = rank + 1
        suffixes[i]['rank'] = rank
    #assigning next ranks
    for i in range(0,n):
      next_index = int(suffixes[i]['index']+k/2)
      index =  [ind for ind, suffix in enumerate(suffixes) if suffix["index"] == next_index]
      suffixes[i]['next_rank'] = suffixes[index[0]]['rank'] if  index else -1
    #sort the suffixes
    suffixes = sorted(suffixes, key = lambda i: (i['rank'], i['next_rank']))
    k = 2*k
  return suffixes
  


#testing 
str = "ball"
suffixes = suffixArray(str)
SA = []
SA_index = []
for i in range(0, len(suffixes)):
  SA_index.append(suffixes[i]['index'])
  SA.append(str[suffixes[i]['index']:])

print(SA_index)
print(SA)

Output

[1, 0, 3, 2] [‘all’, ‘ball’, ‘l’, ‘ll’]