Cod sursa(job #3362466)

Utilizator JenJenCristache Ion JenJen Data 9 august 2026 12:21:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

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

string a, b;

const long long BASE = 31;
const long long MOD = 1000000021;

long long hashing(const string& s)
{
    long long val = 0;
    for (int i = 0; i < s.size(); i++)
    {
        val = (val * BASE % MOD + (unsigned char)s[i]) % MOD;
    }

    return val;
}

long long nr;
vector <int> poz;

int main()
{
    in >> a >> b;

    long long ans = hashing(a);

    long long rez = 0;
    for (int i = 0; i < a.size(); i++)
    {
        rez = (rez * BASE % MOD + (unsigned char)b[i]) % MOD;
    }

    if(ans == rez)
    {
        poz.push_back(0);
        nr++;
    }

    long long BASEE = 1;

    for (int i = 0; i < a.size() - 1; i++)
    {
        BASEE = (BASEE * BASE) % MOD;
    }

    for (int i = a.size(); i < b.size(); i++)
    {
        rez = (rez - ((unsigned char)b[i - a.size()] * BASEE % MOD) + MOD) % MOD;
        rez = rez * BASE % MOD;
        rez = (rez + (unsigned char)b[i]) % MOD;

        if (rez == ans)
        {
            nr++;
            poz.push_back(i - a.size() + 1);
        }
    }

    out << nr << "\n";

    for (int i = 0; i < min(1000LL, (long long)poz.size()); i++)
    {
        out << poz[i] << " ";
    }
    return 0;
}