Cod sursa(job #1533246)

Utilizator daneel95Holteiu Daniel-Ninel daneel95 Data 22 noiembrie 2015 12:20:17
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <string.h>
#define M1 100003
#define M2 100847

using namespace std;

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

char a[2000005],b[2000005];
int inceputuri[200005];

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

    in>>b>>a;

    x=strlen(a);
    y=strlen(b);
    if(y>x) out<<'0';
    else{
        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<=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;
}