prefix_function

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

int main() {
    std::string substr, str;
    std::cin >> substr;
    std::cin >> str;
    substr += '#';
    int len = substr.size();
    std::vector<int> prefix(len);
    for (int i = 1; i < len; i++) {
        int k = prefix[i - 1];
        while (k > 0 && substr[i] != substr[k])
        {
            k = prefix[k - 1];
        }
        if (substr[i] == substr[k]) {
            k++;
        }
        prefix[i] = k;
    }
    int k = 0;
    if (str[0] == substr[0]) {
        k = 1;
    }
    if (k == len - 1) {
        std::cout << 0 << ' ';
    }
    for (int i = 1; i < str.size(); i++) {
        while (k > 0 && str[i] != substr[k]) {
            k = prefix[k - 1];
        }
        if (str[i] == substr[k]) {
            k++;
        }
        if (k == len - 1) {
            std::cout << i - len + 2 << ' ';
        }
    }
    return 0;
}