Cod sursa(job #3340604)

Utilizator 0021592Grecu rares 0021592 Data 15 februarie 2026 11:42:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <string>
#include <vector>
#define int long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MOD1 = 666013, MOD2 = 1e6+7, p = 97;
int nr;
string a, b;
vector<int> v;
int poz, i, hash_a_1, hash_a_2, hash_b_1, hash_b_2, p1, p2;
int32_t main()
{
    getline(in, a);
    getline(in, b);
    if (a.size() > b.size())
    {
        out << 0;
        return 0;
    }
    p1 = p2 = 1;
    for (i = 0; i < a.size(); i++)
    {
        hash_a_1 = ((hash_a_1*p)%MOD1 + a[i]%MOD1)%MOD1;
        hash_a_2 = ((hash_a_2*p)%MOD2 + a[i]%MOD2)%MOD2;

        hash_b_1 = ((hash_b_1*p)%MOD1 + b[i]%MOD1)%MOD1;
        hash_b_2 = ((hash_b_2*p)%MOD2 + b[i]%MOD2)%MOD2;

        if (i > 0)
        {
            p1 = (p1*p)%MOD1;
            p2 = (p2*p)%MOD2;
        }
    }
    if (hash_a_1 == hash_b_1 && hash_a_2 == hash_b_2)
    {
        v.push_back(0);
        nr++;
    }
    for (i = a.size(); i < b.size(); i++)
    {
        hash_b_1 = (((hash_b_1 + MOD1 - (b[i-a.size()]*p1)%MOD1)*p%MOD1)+b[i])%MOD1;
        hash_b_2 = (((hash_b_2 + MOD2 - (b[i-a.size()]*p2)%MOD2)*p%MOD2)+b[i])%MOD2;
        if (hash_a_1 == hash_b_1 && hash_a_2 == hash_b_2)
        {
            if (nr < 1000)
                v.push_back(i-a.size()+1);
            nr++;
        }
    }
    out << nr << '\n';
    for (auto ind : v)
        out << ind << ' ';
    return 0;
}