Cod sursa(job #3225706)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 18 aprilie 2024 15:31:42
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 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 = 2e6 + 9;

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

int n, m;
char a[N], b[N];

const int P = 73, M1 = 100007, M2 = 100021;
ll add(ll a, ll b, ll M)
{
    ll x = a + b;
    if(x >= M)x -= M;
    if(x < 0)x += M;
    return x;
}
ll mul(ll x, ll y, ll M)
{
    return (x * y) % M;
}

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

    int hsh1 = 0, hsh2 = 0;
    FOR(i, 0, n - 1)hsh1 = add(mul(hsh1, P, M1), a[i], M1);
    FOR(i, 0, n - 1)hsh2 = add(mul(hsh2, P, M2), a[i], M2);

    int pt1 = 1, pt2 = 1;
    FOR(i, 0, n - 2)pt1 = mul(pt1, P, M1);
    FOR(i, 0, n - 2)pt2 = mul(pt2, P, M2);

    vi ans;

    int cur1 = 0, cur2 = 0;
    FOR(i, 0, n - 1)
    {
        cur1 = add(mul(cur1, P, M1), b[i], M1);
        cur2 = add(mul(cur2, P, M2), b[i], M2);
    }

    if(cur1 == hsh1 && cur2 == hsh2)
        ans.pb(n);

    FOR(i, n, m - 1)
    {
        cur1 = add(mul(add(cur1, - mul(b[i - n], pt1, M1), M1), P, M1), b[i], M1);
        cur2 = add(mul(add(cur2, - mul(b[i - n], pt2, M2), M2), P, M2), b[i], M2);

        if(cur1 == hsh1 && cur2 == hsh2 && ans.size() < 1000)
            ans.pb(i);
    }

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