Cod sursa(job #3337707)

Utilizator jarnea_justinjarnea justin ioan jarnea_justin Data 29 ianuarie 2026 16:13:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>
using namespace std;
#define mod1 1000000007
#define mod2 1000000009
#define int unsigned long long
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
int ha1,ha2,hb1,hb2,p1=1,p2=1;
int sza,szb,nr;
vector<int> sol;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    f>>a>>b;
    sza=a.size();
    szb=b.size();
    if(sza>szb)
    {
        g<<0;
        return 0;
    }
    for(int i=0;i<sza;i++)
    {
        ha1=((ha1*37)%mod1+a[i])%mod1;
        ha2=((ha2*31)%mod2+a[i])%mod2;
        if(i!=0)
        {
            p1=(p1*37)%mod1;
            p2=(p2*31)%mod2;
        }
    }
    for(int i=0;i<sza;i++)
    {
        hb1=((hb1*37)%mod1+b[i])%mod1;
        hb2=((hb2*31)%mod2+b[i])%mod2;
    }
    if(ha1==hb1 && ha2==hb2)
        sol.push_back(0);

    for(int i=sza;i<=szb;i++)
    {
        hb1=((37*(hb1+mod1-(b[i-sza]*p1)%mod1))%mod1+b[i])%mod1;
        hb2=((31*(hb2+mod2-(b[i-sza]*p2)%mod2))%mod2+b[i])%mod2;
        if(ha1==hb1 && ha2==hb2)
            sol.push_back(i-sza+1);
    }
    g<<sol.size()<<'\n';
    for(auto x:sol)
        g<<x<<" ";
    return 0;
}