s = "toomanyapples$"
n = len(s)
suffixes = [s[i:] for i in range(len(s))]
ssuffixes = sorted(suffixes)
sa = [n-len(ssuffixes[i]) for i in range(n)]

# for i in range(n):
#     print("{:2}:{}".format(i, ssuffixes[i]))



sam1 = [None]*n
for i in range(len(sa)):
    sam1[sa[i]] = i

print("{:>5}:".format("SA"), end='')
print(" ".join(["{:>2}".format(i) for i in sa]))
print()
print("{:>5}:".format("i"), end='')
print(" ".join(["{:>2}".format(i) for i in range(n)]))
print("{:>5}:".format("s"), end='')
print(" ".join(["{:>2}".format(c) for c in s]))
print("{:>5}:".format("rank"), end='')
print(" ".join(["{:>2}".format(sam1[i]) for i in range(n)]))

for j in range(len(sa)):
    i = sa[j]
    print("{:2}:".format(j), end='')
    print(s[i:], end='')
    print("\u001b[31m", end='')
    print(s[:i])
    print("\u001b[0m", end='')



print()
print("{:>5}:".format("BWT"), end='')
print(" ".join(["{:>2}".format(s[x-1]) for x in sa]))