Cod sursa(job #3225709)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 18 aprilie 2024 15:39:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 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;
string a, b;

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 = a.size(), m = b.size();

    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, 1, n)pt1 = mul(pt1, P, M1);
    FOR(i, 1, n)pt2 = mul(pt2, P, M2);

    vi ans;int nr = 0;
    int cur1 = 0, cur2 = 0;
    FOR(i, 0, m - 1)
    {
        cur1 = add(mul(cur1, P, M1), b[i], M1);
        cur2 = add(mul(cur2, P, M2), b[i], M2);
        if(i >= n)cur1 = add(cur1, - mul(b[i - n], pt1, M1), M1);
        if(i >= n)cur2 = add(cur2, - mul(b[i - n], pt2, M2), M2);
        if(i + 1 >= n && cur1 == hsh1 && cur2 == hsh2 && ans.size() < 1000)ans.pb(i), nr ++;
    }

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