Cod sursa(job #3340906)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 17 februarie 2026 01:43:47
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int base = 127;
const int mod1 = 666013;
const int mod2 = 1e9 + 7;

vector <int> sol;

void rabinkarp (string a, string b)
{
    int n = a.size ();
    int m = b.size ();

    if (n > m)
    {
        fout << 0;
        return;
    }

    int hashA1 = 0, hashA2 = 0;
    int power1 = 1, power2 = 1;

    for (int i = 0; i < n; i++)
    {
        hashA1 = (hashA1 * base + a[i]) % mod1;
        hashA2 = (hashA2 * base + a[i]) % mod2;

        if (i != n - 1)
        {
            power1 = power1 * base % mod1;
            power2 = power2 * base % mod2;
        }
    }

    int hashB1 = 0, hashB2 = 0;

    for (int i = 0; i < n; i++)
    {
        hashB1 = (hashB1 * base + b[i]) % mod1;
        hashB2 = (hashB2 * base + b[i]) % mod2;
    }

    if (hashB1 == hashA1 && hashB2 == hashA2)
        sol.push_back (0);

    for (int i = n; i < m; i++)
    {
        hashB1 = ((hashB1 - b[i - n] * power1 % mod1 + mod1) * base + b[i]) % mod1;
        hashB2 = ((hashB2 - b[i - n] * power2 % mod2 + mod2) * base + b[i]) % mod2;

        if (hashB1 == hashA1 && hashB2 == hashA2)
            sol.push_back (i - n + 1);
    }
}

signed main ()
{
    string a, b;
    fin >> a >> b;

    rabinkarp (a, b);

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

    int limit = min ((int)sol.size (), 1000LL);
    for (int i = 0; i < limit; i++)
        fout << sol[i] << " ";

    return 0;
}