Cod sursa(job #3332296)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 5 ianuarie 2026 22:36:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int BASE = 53, MOD = 1e9 + 7;

int powlg(int a, int b)
{
    int rez = 1;
    while (b)
    {
        if (b & 1)
        {
            rez = 1LL * rez * a % MOD;
        }
        b >>= 1;
        a = 1LL * a * a % MOD;
    }
    return rez;
}

int main()
{
    string a, b;
    f >> a >> b;
    int hashA = 0, pCrt = 1;
    for (auto ch: a)
    {
        hashA = (hashA + 1LL * pCrt * ch) % MOD;
        pCrt = 1LL * pCrt * BASE % MOD;
    }

    int hashB = 0, invMod = powlg(BASE, MOD - 2), countMatches = 0;
    pCrt = 1;
    vector<int> pozSol;
    for (int i = 0; i < b.size(); i++)
    {
        if (i < a.size())
        {
            hashB = (hashB + 1LL * pCrt * b[i]) % MOD;
            pCrt = 1LL * pCrt * BASE % MOD;
        }
        else
        {
            hashB = 1LL * (hashB - b[i - a.size()] + 1LL * b[i] * pCrt + MOD) * invMod % MOD;
        }
        if (hashB == hashA)
        {
            countMatches++;
            if (pozSol.size() < 1000)
                pozSol.push_back(i - a.size() + 1);
        }
    }
    g << countMatches << '\n';
    for (auto poz: pozSol)
    {
        g << poz << ' ';
    }
    return 0;

}