Cod sursa(job #1112922)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 20 februarie 2014 10:15:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <string.h>
#define DIM 2000010
#define P 73
#define MOD1 100007
#define MOD2 100008
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[DIM], b[DIM], s[DIM];
int na, nb, ha1, ha2, p1, p2, hb1, hb2, i, nr;
int main(){
    f.get(a, DIM);
    f.get();
    f.get(b, DIM);
    f.get();
    f.close();
    na=strlen(a);
    nb=strlen(b);
    p1=p2=1;
    ha1=ha2=0;
    for(i=0; i<na; i++)
    {
        ha1=(ha1*P+a[i])%MOD1;
        ha2=(ha2*P+a[i])%MOD2;
        if (i!=0)
            p1=(p1*P)%MOD1,
            p2=(p2*P)%MOD2;
    }
    if(na>nb)
    {
        g<<"0\n";
        return 0;
    }
    for(i=0; i<na; i++)
    {
        hb1=(hb1*P+b[i])%MOD1;
        hb2=(hb2*P+b[i])%MOD2;
    }
    if(hb1==ha1 && hb2==ha2)
    {
        s[0]=1;
        nr++;
    }
    for(i=na; i<nb; i++)
    {
        hb1=((hb1-(b[i-na]*p1)%MOD1+MOD1)*P+b[i])% MOD1;
        hb2=((hb2-(b[i-na]*p2)%MOD2+MOD2)*P+b[i])% MOD2;
        if(hb1==ha1 && hb2==ha2)
        {
            s[i-na+1]=1;
            nr++;
        }
    }
    g<<nr<<"\n";
    nr=0;
    for(i=0; i<nb && nr<1000; i++)
        if(s[i])
        {
            nr++;
            g<<i<<' ';
        }
    g<<"\n";
    return 0;
}