Cod sursa(job #3332297)

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

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int BASE1 = 53, BASE2 = 73, 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 hash1A = 0, hash2A = 0, pCrt1 = 1, pCrt2 = 1;
    for (auto ch: a)
    {
        hash1A = (hash1A + 1LL * pCrt1 * ch) % MOD;
        hash2A = (hash2A + 1LL * pCrt2 * ch) % MOD;
        pCrt1 = 1LL * pCrt1 * BASE1 % MOD;
        pCrt2 = 1LL * pCrt2 * BASE2 % MOD;
    }

    int hash1B = 0, hash2B = 0, invMod1 = powlg(BASE1, MOD - 2), invMod2 = powlg(BASE2, MOD - 2);
    pCrt1 = 1;
    pCrt2 = 1;
    vector<int> pozSol;
    int countMatches = 0;
    for (int i = 0; i < b.size(); i++)
    {
        if (i < a.size())
        {
            hash1B = (hash1B + 1LL * pCrt1 * b[i]) % MOD;
            hash2B = (hash2B + 1LL * pCrt2 * b[i]) % MOD;
            pCrt1 = 1LL * pCrt1 * BASE1 % MOD;
            pCrt2 = 1LL * pCrt2 * BASE2 % MOD;
        }
        else
        {
            hash1B =
                    1LL * (hash1B - b[i - a.size()] + 1LL * b[i] * pCrt1 + MOD) * invMod1 % MOD;
            hash2B =
                    1LL * (hash2B - b[i - a.size()] + 1LL * b[i] * pCrt2 + MOD) * invMod2 % MOD;
        }
        if (hash1B == hash1A)
        {
            countMatches++;
            if (pozSol.size() < 1000)
                pozSol.push_back(i - a.size() + 1);
        }
    }
    g << countMatches << '\n';
    for (auto poz: pozSol)
    {
        g << poz << ' ';
    }
    return 0;

}