Cod sursa(job #1527944)

Utilizator daneel95Holteiu Daniel-Ninel daneel95 Data 18 noiembrie 2015 21:26:26
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <string.h>
#define M1 100129
#define M2 100907

using namespace std;

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

char a[2000005],b[2000005];

int main()
{
    int i,x,y,hashb1=0,hashb2=0,hasha1=0,hasha2=0,q=0,aux1=0;
    int nr=0,inceputuri[1001],p=0,putmax1=1,putmax2=1,aux2=0;

    in>>b>>a;

    x=strlen(a);
    y=strlen(b);

    for(i=0;i<y;i++)
    {
        hashb1=(hashb1*256+b[i])%M1;
        hashb2=(hashb2*256+b[i])%M2;
        hasha1=(hasha1*256+a[i])%M1;
        hasha2=(hasha2*256+a[i])%M2;
        putmax1=(putmax1*256)%M1;
        putmax2=(putmax2*256)%M2;
    }

    if((hasha1==hashb1) && (hasha2==hashb2))
    {
        nr++;
        inceputuri[p]=0;
        p++;
    }
    //out<<"hasha1= "<<hasha1<<"\t hasha2= "<<hasha2<<"\t hashb1= "<<hashb1<<"\t hashb2= "<<hashb2<<"\n";
    for(i=y;i<x;i++)
    {
        aux1=(a[q]*putmax1)%M1;
        aux2=(a[q]*putmax2)%M2;
        q++;
        hasha1=((hasha1*256+a[i])%M1-aux1+M1)%M1;
        hasha2=((hasha2*256+a[i])%M2-aux2+M2)%M2;
        //out<<"hasha1= "<<hasha1<<"\t hasha2= "<<hasha2<<"\n";
        if((hasha1==hashb1) && (hasha2==hashb2))
        {
            nr++;
            inceputuri[p]=q;
            p++;
        }
    }

    out<<nr<<"\n";
    if(nr==0){
    if(nr<=1000)
    {
        for(i=0;i<nr;i++) out<<inceputuri[i]<<" ";
    }else for(i=0;i<1000;i++) out<<inceputuri[i]<<" ";
    }
    in.close();
    out.close();
    return 0;
}