Cod sursa(job #3332207)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 4 ianuarie 2026 23:48:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 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);
    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 && pozSol.size() < 1000)
        {
            pozSol.push_back(i - a.size() + 1);
        }
    }
    g << pozSol.size() << '\n';
    for (auto poz: pozSol)
    {
        g << poz << ' ';
    }
    return 0;

}