Seminar14

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

std::vector<int> SuffixArray(const std::string& s) {
  int n = s.length() + 1;
  // Отсортировать по первой букве.
  std::vector<int> c(std::max(256, n));
  for (int i = 0; i < n; ++i) ++c[static_cast<uint8_t>(s[i])];
  for (int i = 1; i < c.size(); ++i) c[i] += c[i - 1];
  std::vector<int> smass(n);
  for (int i = n - 1; i >= 0; --i) {
    smass[--c[static_cast<uint8_t>(s[i])]] = i;
  }

  std::vector<int> pockets(n);
  c.assign(n, 0);
  // Заполним первые номера групп и их концы.
  int current_group = 0;
  for (int i = 0; i < n; ++i) {
    if (i != 0 && s[smass[i]] != s[smass[i - 1]]) ++current_group;
    pockets[smass[i]] = current_group;
    c[current_group] = i + 1;  // Текущий конец группы
  }

  // Отсортируем по всем остальным
  std::vector<int> smass_new(n);
  std::vector<int> new_pockets(n);
  for (int k = 1; k < n; k <<= 1) {
    for (int i = n - 1; i >= 0; --i) {
      int shifted_suffix = (smass[i] - k + n) % n;
      int pocket = pockets[shifted_suffix];
      smass_new[--c[pocket]] = shifted_suffix;
    }
    std::swap(smass, smass_new);

    // Заполним первые номера групп и их концы.
    current_group = 0;
    c.assign(n, 0);
    for (int i = 0; i < n; ++i) {
      if (i != 0 && (pockets[smass[i]] != pockets[smass[i - 1]] ||
          pockets[(smass[i] + k) % n] != pockets[(smass[i - 1] + k) % n])) {
        ++current_group;
      }
      new_pockets[smass[i]] = current_group;
      c[current_group] = i + 1;
    }
    std::swap(pockets, new_pockets);
  }
  return smass;
}

std::vector<int> Kasai(const std::vector<int>& smass, const std::string& s) {
  // Построим обратное отображение – для каждого суффикса его позиция в smass.
  // (на самом деле это pockets в конце построения).
  std::vector<int> o(smass.size());
  for (int i = 0; i < smass.size(); ++i) o[smass[i]] = i;

  std::vector<int> lcp(smass.size());
  int cur_lcp = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (o[i] == smass.size() - 1) continue;
    int inext = smass[o[i] + 1];
    // Не проверяем выход за границу строки, так как в конце спасительный \0
    for (; s[i + cur_lcp] == s[inext + cur_lcp]; ++cur_lcp);
    lcp[o[i]] = cur_lcp;
    cur_lcp = std::max(0, cur_lcp - 1);
  }
  return lcp;
}

int main() {
  std::string s; std::cin >> s;
  std::vector<int> smass = SuffixArray(s);
  for (int v : smass) std::cout << v << "\n";
  std::cout << "Kasai\n";
  std::vector<int> lcp = Kasai(smass, s);
  for (int v : lcp) std::cout << v << "\n";
  return 0;
}