Cod sursa(job #1855583)

Utilizator pusi23Faier Andreea pusi23 Data 23 ianuarie 2017 19:44:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int na,nb,i,ha1,ha2,hb1,hb2,p1,p2,bz,nr,d1,d2,c;
char a[2000002],b[2000002],x[2000002];
int main()
{
    f>>a;
    na=strlen(a);
    bz=73;
    p1=100007;
    p2=100021;
    ha1=0;
    ha2=0;
    nr=0;
    for(i=0;i<=na-1;i++)
    {
        ha1=(ha1*bz+a[i])%p1;
        ha2=(ha2*bz+a[i])%p2;
    }
    f>>b;
    nb=strlen(b);
    hb1=0; hb2=0;
    for(i=0;i<=na-1;i++)
    {
        hb1=(hb1*bz+b[i])%p1;
        hb2=(hb2*bz+b[i])%p2;
    }
    if(hb1==ha1&&hb2==ha2)
    {
        nr++;
        x[0]=1;
    }
    d1=1; d2=1;
    for(i=1;i<=na-1;i++)
    {
        d1=(d1*bz)%p1;
        d2=(d2*bz)%p2;
    }
    for(i=na;i<=nb-1;i++)
    {
        hb1=((hb1-(d1*b[i-na])%p1+p1)*bz+b[i])%p1;
        hb2=((hb2-(d2*b[i-na])%p2+p2)*bz+b[i])%p2;
        if(hb1==ha1&&hb2==ha2)
        {
            nr++;
            x[i-na+1]=1;
        }
    }
    g<<nr<<'\n';
    c=0;
    for(i=0;i<=nb-na;i++)
    {
        if(x[i]==1)
        {c++;
        if(c<1001) g<<i<<" ";
        }
    }
    f.close();
    g.close();
    return 0;
}