Алгоритм Кнута-Морриса-Пратта (КМП)

def f(p):
    m = len(p)
    A = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = A[j - 1]
        if p[i] == p[j]:
            j += 1
        A[i] = j
    return A

def kmp(s, p):
    n = len(s)
    m = len(p)
    A = f(p)
    Z = []
    j = 0
    for i in range(n):
        while j > 0 and s[i] != p[j]:
            j = A[j - 1]
        if s[i] == p[j]:
            j += 1
        if j == m:
            Z.append(i - m + 1)
            j = A[j - 1]
    return Z

s = input()
p = input()
ANS = kmp(s, p)
print(len(ANS))
print(*[x + 1 for x in ANS])

#include <bits/stdc++.h>
using namespace std;

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

vector<int> kmp(const string& s, const string& p) {
    int n = s.size();
    int m = p.size();
    vector<int> A = f(p);
    vector<int> Z;
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j > 0 && s[i] != p[j]) {
            j = A[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            Z.push_back(i - m + 1);
            j = A[j - 1];
        }
    }
    return Z;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string s, p;
    cin >> s >> p;
    
    vector<int> ans = kmp(s, p);
    cout << ans.size() << "\n";
    for (int x : ans) {
        cout << x + 1 << " ";
    }
    
    return 0;
}