Cod sursa(job #3340904)

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

using namespace std;

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

const int nmax = 2e6 + 5;

const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int baza = 131;

int val (char c)
{
    if (c >= 'a' && c <= 'z')
        return c - 'a' + 1;
    if (c >= 'A' && c <= 'Z')
        return c - 'A' + 27;
    return c - '0' + 53;
}

string a, b;

int h1[nmax], h2[nmax], p1[nmax], p2[nmax];

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

    int n = a.size ();
    int m = b.size ();

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

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

    p1[0] = p2[0] = 1;

    for (int i = 1; i <= m; i++)
    {
        p1[i] = p1[i - 1] * baza % mod1;
        p2[i] = p2[i - 1] * baza % mod2;

        h1[i] = (h1[i - 1] * baza + val (b[i - 1])) % mod1;
        h2[i] = (h2[i - 1] * baza + val (b[i - 1])) % mod2;
    }

    vector <int> sol;

    for (int i = 0; i + n <= m; i++)
    {
        int cur1 = (h1[i + n] - h1[i] * p1[n] % mod1 + mod1) % mod1;
        int cur2 = (h2[i + n] - h2[i] * p2[n] % mod2 + mod2) % mod2;

        if (cur1 == hashA1 && cur2 == hashA2)
            sol.push_back (i);
    }

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

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

    return 0;
}