Seminar11

#include <iostream>
#include <vector>

std::vector<int> Prefix(const std::string& s) {
  std::vector<int> pi(s.size());
  int prev_pi = 0;
  for (size_t i = 1; i < s.size();) {
    if (s[i] == s[prev_pi]) {
      pi[i] = ++prev_pi;
      ++i;
    } else if (prev_pi == 0) {
      pi[i] = 0;
      ++i;
    } else {
      prev_pi = pi[prev_pi - 1];
    }
  }
  return pi;
}

std::vector<int> ZFunction(const std::string& s) {
  std::vector<int> z(s.size());
  z[0] = s.size();
  int l = 0, r = 0;
  for (int i = 1; i < s.size(); ++i) {
    if (i >= r) {
      while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) ++z[i];
      l = i;
      r = i + z[i];
    } else {
      if (z[i - l] < r - i) z[i] = z[i - l];
      else if (z[i - l] > r - i) z[i] = r - i;
      else {
        z[i] = z[i - l];
        while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) ++z[i];
        l = i;
        r = i + z[i];
      }
    }
  }
  return z;
}

std::vector<int> ZFunction2(const std::string& s) {
  std::vector<int> z(s.size());
  z[0] = s.size();
  int l = 0, r = 0;
  for (int i = 1; i < s.size(); ++i) {
    if (i < r) {
      z[i] = std::min(z[i - l], r - i);
    }
    while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] > r) {
      l = i;
      r = i + z[i];
    }
  }
  return z;
}

int main() {
  std::string s; std::cin >> s;
//  auto pi = Prefix(s);
  auto z = ZFunction2(s);
  for (int x : z) std::cout << x;
  return 0;
}