fast_bwt.py

#text = 'BANANA'
text = 'GAATTCAAGCTTGGATCCGGAAAGATCTGATC' 
t = text + '^'
N = len(t)

# L is the suffix array
L = list()

# i: index to walk current suffix along text
# j: indexes for sorted suffix already in suffix array
# k: enumeration of L, to give insertion point

def doOne(i,L):
  for k,j in enumerate(L):
    n = 0
    while t[i+n] == t[j+n]:
      n += 1
    if t[i+n] < t[j+n]:
      L.insert(k,i)
      return
  L.append(i)

for i in range(1,N):
  doOne(i,L)

bwt = ''.join([t[j-1] for j in L])
print bwt, '\n'
for k,j in enumerate(L):
  if k and not k % 10:
    print
  print '%3d' % j,