Cod sursa(job #3151898)

Utilizator Summer05Cocut Alexandru Summer05 Data 23 septembrie 2023 06:08:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
/// Knuth - Morris - Pratt

#include <bits/stdc++.h>

#pragma GCC optimize("fast-math")
#pragma GCC target("avx2")

#define ll long long
#define pll pair<ll, ll>
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define sz size()
#define all(x) (x).begin() + 1, (x).end()
#define allrev(x) (x).rbegin(), (x).rend() - 1
#define all0(x) (x).begin(), (x).end()
#define allrev0(x) (x).rbegin(), (x).rend()

using namespace std;

void solve()
{
    string text, pattern;
    cin >> pattern >> text;

    ll n = text.sz;
    ll m = pattern.sz;

    vector<ll> pf(m);
    pf[0] = 0;

    for (ll i = 1, j = 0; i < m; i++)
    {
        while (pattern[i] != pattern[j] && j > 0)
            j = pf[j - 1];

        if (pattern[i] == pattern[j])
            pf[i] = ++j;
        else
            pf[i] = 0;
    }

    vector<ll> ans;
    for (ll i = 0, j = 0; i < n; i++)
    {
        while (text[i] != pattern[j] && j > 0)
            j = pf[j - 1];

        if (text[i] == pattern[j])
            ++j;

        if (j == m)
        {
            j = pf[j - 1];
            ans.pb(i - m + 1);
        }
    }

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

    for (ll z : ans)
        cout << z << ' ';
}

int main(void)
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

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

    ///ll tt; cin >> tt; while(tt--)
        solve();

    return 0;
}