Build a suffix array from string

suffixArray.py

#!/usr/bin/env python3

import sys
from operator import itemgetter

input = sys.stdin.readline

def insr():
  s = input()
  return(list(s[:len(s) - 1]))

def suffixArray(s):
  s += "$"
  n = len(s)
  if n == 0:
    return []

  p = [0] * n
  c = [0] * n
  a = [0] * n

  for i in range(n):
    a[i] = (s[i], i)

  a.sort()

  for i in range(n):
    p[i] = a[i][1]

  c[p[0]] = 0
  for i in range(1,n):
    if a[i][0] == a[i-1][0]:
      c[p[i]] = c[p[i-1]]
    else:
      c[p[i]] = c[p[i-1]] + 1

  k = 0
  while ((1<<k) < n):
    a = [None] * n
    for i in range(n):
      a[i] = ((c[i], c[(i+(1 << k)) % n]), i)

    a.sort()

    for i in range(n):
      p[i] = a[i][1]

    c[p[0]] = 0
    for i in range(1,n):
      if a[i][0] == a[i-1][0]:
        c[p[i]] = c[p[i-1]]
      else:
        c[p[i]] = c[p[i-1]] + 1

    k += 1

  for c in p:
    print(c, end=' ')


if __name__ == "__main__":
  s = insr()
  suffixArray(s)
  print()