HA40_1

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

class PrefixFunctionCalculator {
private:
    std::string s;
    std::vector<int> pi;

    void computePrefixFunction() {
        int n = s.size();
        pi.resize(n, 0);

        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) {
                j = pi[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            pi[i] = j;
        }
    }

public:
    explicit PrefixFunctionCalculator(const std::string &str)
            : s(str)
    {
        computePrefixFunction();
    }

    const std::vector<int>& getPrefixFunction() const {
        return pi;
    }
};

int main() {
    std::string input;
    std::cin >> input;

    PrefixFunctionCalculator calculator(input);

    const std::vector<int>& prefixFunc = calculator.getPrefixFunction();

    for (size_t i = 0; i < prefixFunc.size(); ++i) {
        std::cout << prefixFunc[i];
        if (i + 1 < prefixFunc.size()) {
            std::cout << ' ';
        }
    }
    std::cout << std::endl;

    return 0;
}