Seminar14

#include <iostream>
#include <string>
#include <vector>

std::vector<int> SuffixArray(const std::string& s) {
  const int n = s.size() + 1;
  std::vector<int> suff_mass(n);
  // Отсортируем по первому символу.
  std::vector<int> c(std::max(256, n));
  for (int i = 0; i <= s.size();++i) c[s[i]]++;
  for (int i = 1; i < 256; ++i) c[i] += c[i - 1];
  for (int i = n - 1; i >= 0; --i) suff_mass[--c[s[i]]] = i;

  // Первое заполнение карманов и концов групп
  std::vector<int> pockets(n);
  pockets[suff_mass[0]] = 0;
  c[0] = 1;
  int curr_pocket = 0;
  for (int i = 1; i < n; ++i) {
    if (s[suff_mass[i]] != s[suff_mass[i - 1]]) ++curr_pocket;
    pockets[suff_mass[i]] = curr_pocket;
    c[curr_pocket] = i + 1;
  }

  for (int k = 0; (1 << k) < n; ++k) {
    std::vector<int> b(n);
    for (int i = n - 1; i >= 0; --i) {
      int curr_suff = (suff_mass[i] - (1 << k) + n) % n;
      b[--c[pockets[curr_suff]]] = curr_suff;
    }
    suff_mass = std::move(b);
    // Обновим pockets и c.
    std::vector<int> new_pockets(n);
    int curr_pocket = 0;
    for (int i = 0; i < n; ++i) {
      if (i > 0 && (pockets[suff_mass[i]] != pockets[suff_mass[i - 1]] ||
          pockets[(suff_mass[i] + (1 << k)) % n] != pockets[(suff_mass[i - 1] + (1 << k)) % n]))
        ++curr_pocket;
      new_pockets[suff_mass[i]] = curr_pocket;
      c[curr_pocket] = i + 1;
    }
    pockets = std::move(new_pockets);
  }

  return suff_mass;
}

int main() {
  std::string s; std::cin >> s;
  std::vector<int> suff_mass = SuffixArray(s);
  for (int suff : suff_mass) {
    std::cout << s.substr(suff) << std::endl;
  }
  return 0;
}