Cod sursa(job #3348960)

Utilizator CreditKing69Bogdan Moldovan CreditKing69 Data 24 martie 2026 20:30:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const long long mod1 = 1000000007;
const long long mod2 = 1000000009;
const long long baza = 67676767;

int main()
{
    string a, b;
    fin >> a >> b;

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

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

    long long hashA1 = 0, hashA2 = 0;
    long long hashB1 = 0, hashB2 = 0;
    long long put1 = 1, put2 = 1;

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

        hashB1 = (hashB1 * baza + b[i]) % mod1;
        hashB2 = (hashB2 * baza + b[i]) % mod2;

        if (i < n - 1)
        {
            put1 = put1 * baza % mod1;
            put2 = put2 * baza % mod2;
        }
    }

    vector<int> rez;
    int cnt = 0;

    if (hashA1 == hashB1 && hashA2 == hashB2)
    {
        cnt++;
        rez.push_back(0);
    }

    for (int i = n; i < m; i++)
    {
        hashB1 = (hashB1 - b[i - n] * put1 % mod1 + mod1) % mod1;
        hashB1 = hashB1 * baza % mod1;
        hashB1 = (hashB1 + b[i]) % mod1;

        hashB2 = (hashB2 - b[i - n] * put2 % mod2 + mod2) % mod2;
        hashB2 = hashB2 * baza % mod2;
        hashB2 = (hashB2 + b[i]) % mod2;

        if (hashA1 == hashB1 && hashA2 == hashB2)
        {
            cnt++;
            if ((int)rez.size() < 1000)
            {
                rez.push_back(i - n + 1);
            }
        }
    }

    fout << cnt << '\n';
    for (auto x : rez)
    {
        fout << x << ' ';
    }

    return 0;
}