Cod sursa(job #2803601)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 20 noiembrie 2021 11:30:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;
#define baza 73
#define mod1 1000007
#define mod2 666013
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string pat,s;
int i;
long long putere1=1,putere2=1,cod1,cod2,curr1,curr2;
int nr,rasp[2000005];
void rabin()
{
    int n=pat.size();
    int m=s.size();

    for(i=0; i<n; i++)
    {
        cod1=(cod1*baza%mod1+(pat[i] ))%mod1;
        cod2=(cod2*baza%mod2+(pat[i] ))%mod2;
        curr1=(curr1*baza%mod1+(s[i] ))%mod1;
        curr2=(curr2*baza%mod2+(s[i] ))%mod2;
        if(i<n-1) {putere1*=baza;putere2*=baza;}
        putere1%=mod1;
                putere2%=mod2;


    }
    if(cod1==curr1&&cod2==curr2)
    {
        rasp[++nr]=0;
    }
    for(i=n; i<m; i++)
    {
        curr1=(curr1-s[i-n]*putere1%mod1)+mod1;
        curr1%=mod1;
        curr1*=baza;
        curr1+=(s[i] );
        curr1%=mod1;

        curr2=(curr2-s[i-n]*putere2%mod2)+mod2;
        curr2%=mod2;
        curr2*=baza;
        curr2+=(s[i] );
        curr2%=mod2;

        if(cod1==curr1&&cod2==curr2)
        {
            rasp[++nr]=i-n+1;

        }

    }
    fout<<nr<<'\n';
nr=min(nr,1000);

for(i=1;i<=nr;i++)fout<<rasp[i]<<" ";

}
int main()
{
    fin>>pat>>s;
    rabin();
    return 0;
}