Cod sursa(job #2752718)

Utilizator RaresPoinaruPoinaru-Rares-Aurel RaresPoinaru Data 19 mai 2021 11:33:08
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int p=73;
const int MOD1=666013;
const int MOD2=100007;
const int MAXN=2000001;
string a,b;
int p1,p2,reza1,reza2,rez1,rez2,na,nb,nr,i;
bool identitate [MAXN];
int main()
{
    fin >>a>>b;
    if (na>nb)
    {
        fout <<0;
        return 0;
    }
    na=a.size ();
    nb=b.size ();
    reza1=0;
    reza2=0;
    p1=1;
    p2=1;
    for (i=0;i<na;++i)
    {
        reza1=(reza1*p+a[i])%MOD1;
        reza2=(reza2*p+a[i])%MOD2;
        if (i>0)
        {
            p1=(p1*p)%MOD1;
            p2=(p2*p)%MOD2;
        }
    }
    rez1=0;
    rez2=0;
    nr=0;
    for (i=0;i<na;++i)
    {
        rez1=(rez1*p+b[i])%MOD1;
        rez2=(rez2*p+b[i])%MOD2;
    }
    if (rez1==reza1 and rez2==reza2)
    {
        identitate[0]++;
        nr++;
    }
    for (i=na;i<nb;++i)
    {
        rez1=((rez1-(b[i-na]*p1)%MOD1)*p+b[i])%MOD1;
        rez2=((rez2-(b[i-na]*p2)%MOD2)*p+b[i])%MOD2;
        if (rez1==reza1 and rez2==reza2)
        {
            identitate[i-na+1]=1;
            nr++;
        }

    }
    fout <<nr<<'\n';
    nr=0;
    for (i=0;i<nb and nr<1000;++i)
    {
        if (identitate[i]==1)
        {
            fout <<i<<' ';
            nr++;
        }
    }
    fin.close ();
    fout.close ();
    return 0;
}