Cod sursa(job #2977610)

Utilizator gabriel.9619Gabriel Stefan Tita gabriel.9619 Data 11 februarie 2023 23:14:18
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <cstring>
#define dim 2000001
#define mod1 999997
#define mod2 1000003
#define p 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[dim], b[dim];
int sol[dim];

int main()
{
    int p1, p2, n, i, ha1, ha2, hb1, hb2, la, lb;
    p1=p2=1;
    ha1=ha2=hb1=hb2=0;
    fin>>a>>b;
    la=strlen(a);
    lb=strlen(b);
    if(la>lb)
    {
        fout<<0;
    }
    for(i=0;i<la;i++)
    {
        ha1=(ha1*p+a[i])%mod1;
        ha2=(ha2*p+a[i])%mod2;
        hb1=(hb1*p+b[i])%mod1;
        hb2=(hb2*p+b[i])%mod2;
        if(i!=0)
        {
            p1=(p1*p)%mod1;
            p2=(p2*p)%mod2;
        }
    }
    int nr=0;
    if(ha1==hb1&&ha2==hb2)
    {
        nr++;
        sol[nr]=0;
    }
    for(i=la;i<lb;i++)
    {
        hb1=((hb1-(b[i-la]*p1)%mod1+mod1)*p+b[i])%mod1;
        hb2=((hb2-(b[i-la]*p2)%mod2+mod2)*p+b[i])%mod2;
        if(ha1==hb1&&ha2==hb2)
        {
            nr++;
            sol[nr]=i-la+1;
        }
    }
    fout<<nr<<"\n";
    for(i=1;i<=min(nr, 1000);i++)
    {
        fout<<sol[i]<<" ";
    }
    return 0;
}