咳

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

using namespace std;

vector compute_prefix(const string& s) {

int m = s.size();
vector<int> next(m, 0);
for (int i = 1; i < m; ++i) {
    int j = next[i-1];
    while (j > 0 && s[i] != s[j]) {
        j = next[j-1];
    }
    if (s[i] == s[j]) {
        j++;
    }
    next[i] = j;
}
return next;

}

vector kmp_search(const string& text, const string& pattern, const vector& next) {

vector<int> positions;
int n = text.size();
int m = pattern.size();
int j = 0;
for (int i = 0; i < n; ++i) {
    while (j > 0 && text[i] != pattern[j]) {
        j = next[j-1];
    }
    if (text[i] == pattern[j]) {
        j++;
    }
    if (j == m) {
        positions.push_back(i - m + 2); // 转换为1-based索引
        j = next[j-1];
    }
}
return positions;

}

int main() {

ios::sync_with_stdio(false);
cin.tie(nullptr);

string s1, s2;
cin >> s1 >> s2;

vector<int> next = compute_prefix(s2);
vector<int> positions = kmp_search(s1, s2, next);

for (int pos : positions) {
    cout << pos << '\n';
}

for (size_t i = 0; i < next.size(); ++i) {
    if (i > 0) {
        cout << ' ';
    }
    cout << next[i];
}
cout << '\n';

return 0;

}