sufsort.py

def sufcmp(Z,i,j):
  n = len(Z)-i # length of the suffix Z[i..N-1]
  m = len(Z)-j # length of the suffix Z[j..N-1]
  k = min(n,m)
  
  for o in range(k):
    if Z[i+o]<Z[j+o]:
      return -1
    if Z[i+o]>Z[j+o]:
      return 1
    # so all the letters are the same

    if n<m:
      return -1
    else:
      return 1
##############################################################

def sufsort(Z):
  # display the input string
  print(Z)
  N = len(Z)
  # check the length of the input string
  if N <= 0 or N > 30:
    print("length error")
    return
  # check the composition of the input string
  for i in range(N):
    if not (Z[i]=='0' or Z[i]=='1' or Z[i]=='2'):
      print("composition error")
      return
    # so the input string is fine
    # we will keep the suffix indeces in an array y
    # we create array holding 0, 1, 2, ..., N-1
    y = [];
    for i in range(N):
      y.append(i);
      # so we have an array y = [0,1,2,...N-1]
      # we will sort array y[] using bubble sort and comparing i with j
      # by comparing Z[i..N-1] and Z[j..N-1] using the subroutine
      # sufcmp(Z,i,j)
      for i in range(N,0,-1):
        for j in range(1,i):
          k = sufcmp(Z,y[j-1],y[j])
          if k > 0:
            t = y[j-1]
            y[j-1]=y[j]
            y[j]=t
     # display the sorted suffixes
     print("sorted suffixes:")
      for i in range(N):
        print(Z[y[i]:N])