Cod sursa(job #1919354)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 9 martie 2017 19:00:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#define MAXN 2000001
#define BAZA 75
#define MOD1 666013
#define MOD2 666019
char a[MAXN],b[MAXN];
std::vector <int> v;
int main()
{
    FILE *fin,*fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    fscanf(fin,"%s%s",&a,&b);
    int na,nb,nr,ha1,ha2,hb1,hb2,p1,p2;
    na=strlen(a);nb=strlen(b);
    p1=p2=1;nr=hb1=hb2=ha1=ha2=0;
    if(na>nb)
    {
        fprintf(fout,"0");
        goto sf;
    }
    for(int i=0;i<na;i++)
    {
        ha1=(ha1*BAZA+a[i]-'0')%MOD1;
        ha2=(ha2*BAZA+a[i]-'0')%MOD2;
        if(i!=0)
        {
            p1=(p1*BAZA)%MOD1;
            p2=(p2*BAZA)%MOD2;
        }
    }
    for(int i=0;i<na;i++)
    {
        hb1=(hb1*BAZA+b[i]-'0')%MOD1;
        hb2=(hb2*BAZA+b[i]-'0')%MOD2;
    }
    if(ha1==hb1 && ha2==hb2)
    {
        nr++;
        v.push_back(0);
    }
    for(int i=na;i<nb;i++)
    {
        hb1=(((hb1-((b[i-na]-'0')*p1)%MOD1+MOD1)%MOD1)*BAZA+b[i]-'0')%MOD1;
        hb2=(((hb2-((b[i-na]-'0')*p2)%MOD2+MOD2)%MOD2)*BAZA+b[i]-'0')%MOD2;
        if(ha1==hb1 && ha2==hb2)
        {
            nr++;
            v.push_back(i-na+1);
        }
    }
    fprintf(fout,"%d\n",nr);
    nr=std::min(nr,1000);
    for(int i=0;i<nr;i++)
        fprintf(fout,"%d ",v[i]);
    sf:fclose(fin);
    fclose(fout);
    return 0;
}