Cod sursa(job #3251431)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 26 octombrie 2024 00:47:31
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#pragma region TEMPLATES

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;

void init() {
    srand(time(0));
#ifdef ONLINE_JUDGE
    cin.tie(0)->sync_with_stdio(0);
#else
    freopen( "in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
}

#ifdef ONLINE_JUDGE
    #define debug(...) 69420
    #define init_test(...) 69420
#else
void init_test(int t) {
    cerr << "\nTEST #" << t << "\n";
}
template<typename T>
T debug(T n) {
    cerr << n << " ";
    return n;
}
template<typename T, typename... Args>
T debug(T n, Args... args) {
    cerr << n << " ";
    debug(args...);
    return n;
}
void debug() {
    cerr << "\n";
}
#endif

void solve();
int main() {
    init();
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; ++i) {
        init_test(i);
        solve();
    }
}

#pragma endregion TEMPLATES

void solve() {
    // freopen("strmatch.in",  "r", stdin);
    // freopen("strmatch.out", "w", stdout);
    string A, B;
    cin >> A >> B;
    int n = A.size();
    int m = B.size();

    vector<int> pref(n);
    pref[0] = 0;
    for (int i = 1; i < n; ++i) {
        int k = pref[i - 1];
        while (k != 0 && A[i] != A[k]) {
            k = pref[k];
        }
        if (A[k] == A[i]) {
            ++k;
        }
        pref[i] = k;
    }

    int ct = 0;
    vector<int> ans;

    int k = 0;
    for (int i = 0; i < m; ++i) {
        while (k != 0 && B[i] != A[k]) {
            k = pref[k - 1];
        }
        if (B[i] == A[k]) {
            ++k;
        }
        if (k == n) {
            ++ct;
            if (ct <= 1000)
                ans.push_back(i - n + 1);
            k = pref[n - 1];
        }
    }
    cout << ct << "\n";
    for (int i = 0; i < ct; ++i) {
        cout << ans[i] << " ";
    }

}