Cod sursa(job #3358551)

Utilizator Dariuscriss72Popescu Darius Mihai Dariuscriss72 Data 17 iunie 2026 19:29:26
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int hashing1(string s){
    int i,mod=100000007,baza=31,h=0,x;
    for(i=0;i<s.length();i++){
        x=s[i]-'0'+1;
        h=(h*baza+x)%mod;
        if(h<0){
            h+=mod;
        }
    }
    return h;
}
int hashing2(string s){
    int i,mod=100000009,baza=31,h=0,x;
    for(i=0;i<s.length();i++){
        x=s[i]-'0'+1;
        h=(h*baza+x)%mod;
        if(h<0){
            h+=mod;
        }
    }
    return h;
}
int ex(int baza,int put,int mod){
    int r=1;
    baza=baza%mod;
    while(put>0){
        if(put&1){
            r=(r*baza)%mod;
        }
        baza=(baza*baza)%mod;
        put=(put/2)%mod;    
    }
    return r%mod;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string sa,sb;
    int i,win1=0,win2=0,mod1=100000007,mod2=100000009,baza=31,c,hash1,hash2,alen,blen,scaz1,scaz2,ct=0,c1;
    vector<int> cont;
    f>>sa>>sb;
    alen=sa.length();
    blen=sb.length();
    hash1=hashing1(sa);
    hash2=hashing2(sa);
    scaz1=ex(baza,alen-1,mod1);
    scaz2=ex(baza,alen-1,mod2);
    for(i=0;i<alen;i++){
        c=sb[i]-'0'+1;
        win1=(win1*baza+c)%mod1;
        win2=(win2*baza+c)%mod2;
        if(win2<0){
            win2+=mod2;
        }
        if(win1<0){
            win1+=mod1;
        }
    }
    if(win1==hash1 && win2==hash2){
        ct++;
        if(cont.size()<1000){
        cont.push_back(i-alen+1);
        }
    }
    for(i=alen;i<blen;i++){
        c=sb[i]-'0'+1;
        c1=sb[i-alen]-'0'+1;
        win1=(win1-scaz1*c1)%mod1;
        win2=(win2-scaz2*c1)%mod2;
        if(win1<0){
            win1+=mod1;
        }
        if(win2<0){
            win2+=mod2;
        }
        win1=(win1*baza+c)%mod1;
        win2=(win2*baza+c)%mod2;
        if(win1==hash1 && win2==hash2){
            ct++;
            if(cont.size()<1000){
            cont.push_back(i-alen+1);
            }
        }
    }
    g<<ct<<"\n";
    for(auto j:cont){
        g<<j<<" ";
    }
    return 0;
}