Cod sursa(job #3232199)

Utilizator Ciuca_Stefan06Ciuca Stefan Ciuca_Stefan06 Data 29 mai 2024 10:55:36
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <cstring>
#include <fstream>

#define mod1 666013
#define mod2 10003
#define baza 127

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

long long v1,v2,na,nb,h1,h2,i,j,p1,p2,sol[10005],nr;
char a[2000005],b[2000005];

int main()
{
    fin.getline(a,2000005);
    fin.getline(b,2000005);

    na=strlen(a);
    nb=strlen(b);

    p1=p2=1;

    for(i=0;i<na;i++){
        h1=(h1*baza+a[i])%mod1;
        h2=(h2*baza+a[i])%mod2;

        if(i!=0){
            p1=(p1*baza)%mod1;
            p2=(p2*baza)%mod2;
        }
        v1=(v1*baza+b[i])%mod1;
        v2=(v2*baza+b[i])%mod2;
    }

    if(v1==h1 && v2==h2){
            sol[++j]=i-na+1;
            nr++;
        }

    for(i=na;i<nb;++i){
        v1=((v1-(b[i-na]*p1)%mod1+mod1)*baza+b[i])%mod1;
        v2=((v2-(b[i-na]*p2)%mod2+mod2)*baza+b[i])%mod2;

        if(v1==h1 && v2==h2){
            if(j<=1000){sol[++j]=i-na+1;
            nr++;
            }
        }
    }
    fout<<nr<<'\n';
    for(i=1;i<=j;i++)fout<<sol[i]<<' ';
}