Cod sursa(job #3225698)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 18 aprilie 2024 15:13:58
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#define dd long double
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define ll long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int N = 1e5 + 9;

const string TASK("aria");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

int n, m;
string a, b;

const int P = 211, M = 1e9 + 123;
ll add(ll a, ll b)
{
    ll x = a + b;
    if(x >= M)x -= M;
    if(x < 0)x += M;
    return x;
}
ll mul(ll x, ll y)
{
    return (x * y) % M;
}

int main()
{
    cin >> a >> b;
    n = a.size(), m = b.size();

    int hsh = 0;
    FOR(i, 0, n - 1)hsh = add(mul(hsh, P), a[i]);

    int pt = 1;
    FOR(i, 1, n)pt = mul(pt, P);

    vi ans;
    int cur = 0;
    FOR(i, 0, m - 1)
    {
        cur = add(mul(cur, P), b[i]);
        if(i >= n)cur = add(cur, - mul(b[i - n], pt));
        if(cur == hsh && ans.size() < 1000)ans.pb(i);
    }

    cout << ans.size() << '\n';
    for(auto i : ans)cout << i - n + 1 << ' ';
    return 0;
}