#!/usr/bin/env python
# coding: utf-8

# In[1]:


def rotations(t):
    # Return list of rotations of input string t
    tt = t * 2
    return [ tt[i:i+len(t)] for i in range(len(t)) ]


# In[2]:


rotations('cat')


# In[3]:


def bwm(t):
    # Return lexicographically sorted list of t’s rotations
    return sorted(rotations(t))


# In[4]:


bwm('abaaba$')


# In[5]:


print('\n'.join(bwm('abaaba$')))


# In[6]:


def bwtViaBwm(t):
    # Given T, returns BWT(T) by way of the BWM
    return ''.join(map(lambda x: x[-1], bwm(t)))


# In[7]:


bwtViaBwm('abaaba$') # we can see the result equals the last column of the matrix above


# In[8]:


def suffixArray(s):
    satups = sorted([(s[i:], i) for i in range(len(s))])
    return map(lambda x: x[1], satups)

def bwtViaSa(t):
    # Given T, returns BWT(T) by way of the suffix array
    bw = []
    for si in suffixArray(t):
        if si == 0:
            bw.append('$')
        else:
            bw.append(t[si-1])
    return ''.join(bw) # return string-ized version of list bw


# In[9]:


bwtViaBwm('abaaba$'), bwtViaSa('abaaba$') # same result