Cod sursa(job #2711214)

Utilizator dariadragomir23Dragomir Daria dariadragomir23 Data 23 februarie 2021 19:20:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
char a[2000001], b[2000001];
int d=72, potriv[2000001], nr; //10 cif, 26 litere
int main()
{
    f.getline(a, 2000001);
    f.getline(b, 2000001);
    int lg1=strlen(a), lg2=strlen(b);
    if(lg1>lg2)
        {g<<0; return 0;}
    int hasha1=a[0], hasha2=a[0], hashb1=b[0], hashb2=b[0], put1=1, put2=1;
    for(int i=1; i<lg1; i++)
    {
        hasha1=(hasha1*d+a[i])%MOD1;
        hasha2=(hasha2*d+a[i])%MOD2;
        hashb1=(hashb1*d+b[i])%MOD1;
        hashb2=(hashb2*d+b[i])%MOD2;
        put1=(put1*d)%MOD1;
        put2=(put2*d)%MOD2;
    }
    if(hasha1==hashb1&&hasha2==hashb2)
    {
        potriv[0]=1;
        nr++;
    }
    for(int i=lg1; i<lg2; i++)
    {
        hashb1=((hashb1-(b[i-lg1]*put1)%MOD1+MOD1)*d+b[i])%MOD1;
        hashb2=((hashb2-(b[i-lg1]*put2)%MOD2+MOD2)*d+b[i])%MOD2;
        if(hasha1==hashb1&&hasha2==hashb2)
        {
            potriv[i-lg1+1]=1;
            nr++;
        }
    }
    g<<nr<<'\n';
    nr=0;
    for(int i=0;i<lg2&&nr<1000;i++)
        if(potriv[i]==1)
    {
        g<<i<<' ';
        nr++;
    }
    return 0;
}