Cod sursa(job #3340470)

Utilizator paulihno15Ciumandru Paul paulihno15 Data 14 februarie 2026 15:18:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
/*
    Author: Paul Ciumandru
    Hard work beats talent!
*/
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100000
#define MMAX 50000
#define PMAX 524288
#define LOG 18
#define INF_INT 2e9
#define INF_LL 1e18
#define BS 666013
#define MOD 1000000007

#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";

#define ll long long
#define ull unsigned long long
#define dbl double
#define ldb long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piv pair<int, vector<int>>
#define pipii pair<int, pair<pii, pii>>
#define tpl tuple<int, int, int>
#define tpl2 tuple<int, int, vector<int>>
#define vpi vector<pii>

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n, m;
string ptrn, txt;
vector<int> ans;

vector<int> calc_lps(const string &s) {
    int sz = s.size(), j = 0, i = 1;

    vector<int> rez(sz);
    while (i < sz) {
        if (s[i] == s[j]) {
            j++;
            rez[i] = j;
            i++;
        }
        else {
            if (j != 0) {
                j = rez[j - 1];
            }
            else {
                i++;
            }
        }
    }
    return rez;
}

int main() {
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> ptrn >> txt;

    n = txt.size();
    m = ptrn.size();
    vector<int> lps = calc_lps(ptrn);

    int i = 0, j = 0;
    while (i < n) {
        if (txt[i] == ptrn[j]) {
            i++, j++;
        }

        if (j == m) {
            ans.emplace_back(i - m);
            if (ans.size() == 1000) {
                break;
            }
            j = lps[j - 1];
        }
        else if (i < n && txt[i] != ptrn[j]) {
            if (j != 0) {
                j = lps[j - 1];
            }
            else {
                i++;
            }
        }
    }

    fout << ans.size() << '\n';

    for (auto it : ans) {
        fout << it << ' ';
    }
    return 0;
}