A.cpp

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

const size_t alphabet_size = 256;

void BuildLcp(size_t *lcp, const size_t *suf_array, std::string &text) {
  size_t text_size = text.size();
  size_t min_value_lcp = 0;
  auto rsuf_aray = new size_t[text_size];
  for (size_t i = 0; i < text_size; ++i) {
    rsuf_aray[suf_array[i]] = i;  // reverse function
  }
  for (size_t i = 0; i < text_size; ++i) {
    min_value_lcp > 0 ? --min_value_lcp : 0;
    if (rsuf_aray[i] == text_size - 1) {
      min_value_lcp = 0;
      continue;
    }
    size_t j = suf_array[rsuf_aray[i] + 1];
    while ((std::max(i + min_value_lcp, j + min_value_lcp) < text_size) &&
           (text[i + min_value_lcp] == text[j + min_value_lcp])) {
      ++min_value_lcp;
    }
    lcp[rsuf_aray[i]] = min_value_lcp;
  }
  delete[] rsuf_aray;
}

void ContinueBuilding(std::string &text, size_t *suf_array, size_t *classes,
                      size_t num_class) {
  size_t text_size = text.size();
  auto half_suf = new size_t[text_size];
  auto new_classes = new size_t[text_size];
  for (size_t pow = 0; (1 << pow) < text_size; ++pow) {
    std::vector<size_t> cnt(num_class, 0);
    for (size_t i = 0; i < text_size; ++i) {
      half_suf[i] = (suf_array[i] - (1 << pow) + text_size) % text_size;
    }
    for (size_t i = 0; i < text_size; ++i) {
      ++cnt[classes[half_suf[i]]];
    }
    for (size_t i = 1; i < num_class; ++i) {
      cnt[i] += cnt[i - 1];
    }
    for (size_t i = 0; i < text_size; ++i) {
      suf_array[--cnt[classes[half_suf[text_size - 1 - i]]]] =
          half_suf[text_size - 1 - i];
    }

    size_t last_class = 0;
    new_classes[suf_array[0]] = 0;
    size_t mid1;
    size_t mid2;
    for (size_t i = 1; i < text_size; ++i) {
      mid1 = (suf_array[i - 1] + (1 << pow)) % text_size;
      mid2 = (suf_array[i] + (1 << pow)) % text_size;
      if ((classes[suf_array[i]] != classes[suf_array[i - 1]]) ||
          (classes[mid1] != classes[mid2])) {
        ++last_class;
      }
      new_classes[suf_array[i]] = last_class;
    }
    classes = new_classes;
    num_class = last_class + 1;
  }
  delete[] half_suf;
  delete[] new_classes;
}

void BuildSufArray(std::string &text, size_t *suff_array, size_t *classes) {
  size_t text_size = text.size();
  std::vector<size_t> cnt(alphabet_size, 0);
  for (size_t i = 0; i < text_size; ++i) {
    ++cnt[text[i]];
  }
  for (size_t i = 1; i < alphabet_size; ++i) {
    cnt[i] += cnt[i - 1];
  }
  for (size_t i = 0; i < text_size; ++i) {
    suff_array[--cnt[text[i]]] = i;
  }
  size_t last_class = 0;
  classes[suff_array[0]] = 0;
  for (size_t i = 1; i < text_size; ++i) {
    if (text[suff_array[i]] != text[suff_array[i - 1]]) {
      ++last_class;
    }
    classes[suff_array[i]] = last_class;
  }
  ContinueBuilding(text, suff_array, classes, last_class + 1);
}

size_t Solve(std::string &text) {
  size_t text_size = text.size();
  auto suf_array = new size_t[text_size];
  auto classes = new size_t[text_size];
  auto lcp = new size_t[text_size];
  BuildSufArray(text, suf_array, classes);
  BuildLcp(lcp, suf_array, text);
  size_t answ = 0;
  for (size_t i = 0; i < text_size - 1; ++i) {
    answ += text_size - 1 - lcp[i] - suf_array[i + 1];
  }
  delete[] suf_array;
  delete[] classes;
  delete[] lcp;
  return answ;
}

int main() {
  std::string text;
  std::cin >> text;
  text += '#';
  std::cout << Solve(text) << '\n';
  return 0;
}