Cod sursa(job #2695890)

Utilizator AndreibatmanAndrei Croitoriu Andreibatman Data 14 ianuarie 2021 19:57:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#define MOD1 100007
#define MOD2 100021
#define p 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000010],b[2000010];
int poz,i,pozitiea,pozitieb,pozitie,l1,l2,numar,p1,p2,hasha1,hashb1,hasha2,hashb2;
int v[1010];
int main()
{
    fin>>a>>b;
    l1=strlen(a);
    l2=strlen(b);
    if(l1>l2)
    {
        fout<<0;
        return 0;
    }
    p1=p2=1;
    for(i=0;i<l1;i++)
    {
        hasha1=(hasha1*p%MOD1+a[i]%MOD1)%MOD1;
        hasha2=(hasha2*p%MOD2+a[i]%MOD2)%MOD2;

        hashb1=(hashb1*p%MOD1+b[i]%MOD1)%MOD1;
        hashb2=(hashb2*p%MOD2+b[i]%MOD2)%MOD2;
        if(i>0)
        {
            p1=(p1*p)%MOD1;
            p2=(p2*p)%MOD2;
        }
    }
    if(hasha1==hashb1 && hasha2==hashb2)
        v[++numar]=0;
    for(i=l1;i<l2;i++)
    {
        hashb1=(((hashb1+MOD1-(b[i-l1]*p1)%MOD1)*p%MOD1)+b[i])%MOD1;
        hashb2=(((hashb2+MOD2-(b[i-l1]*p2)%MOD2)*p%MOD2)+b[i])%MOD2;
        if(hasha1==hashb1 && hasha2==hashb2)
        {
            numar++;
            if(numar<=1000)
                v[numar]=i-l1+1;
        }
    }
    fout<<numar<<'\n';
    numar=min(numar,1000);
    for(i=1;i<=numar;i++)
        fout<<v[i]<<" ";
    return 0;
}