Cod sursa(job #1320671)

Utilizator eneandradaEne Oana-Andrada eneandrada Data 18 ianuarie 2015 12:10:39
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define mod1 100007
#define mod2 100021

using namespace std;

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

char a[2000010],b[2000010];
int la,lb,sol[2000010],nr;

int main()
{
    f>>a; f>>b;
    la=strlen(a); lb=strlen(b); //lungimile sirurilor
    int i,baza=26,coda=0,codb=0,coda1=0,codb1=0;
    int pa=1,pa1=1; //puterea maxima a lui 26 in scrierea lui a

    for(i=0;i<la;i++)
    {
        coda=(coda*baza+a[i])%mod1;
        coda1=(coda1*baza+a[i])%mod2;
        if(i>0)
            {pa=pa*baza; pa1=pa1*baza;}
    }

    for(i=0;i<la;i++)
    {
        codb=(codb*baza+b[i])%mod1;
        codb1=(codb1*baza+b[i])%mod2;
    }

    if(coda==codb && coda1==codb1)
    {
        sol[0]=1;
        nr++;
    }

    for(i=la;i<lb;i++)
    {
        codb=((codb-(b[i-la]*pa)%mod1 + mod1)*baza+b[i])%mod1;
        codb1=((codb1-(b[i-la]*pa)%mod2 + mod2)*baza+b[i])%mod2;
        if(coda==codb && coda1==codb1)
        {
            sol[i-la+1]=1;
            nr++;
        }
    }
    g<<nr<<endl;
    nr=0;
    for(i=0;i<lb && nr<1000;i++)
        if(sol[i]==1)
            {g<<i<<" ";nr++;}
    g<<endl;
    f.close(); g.close();
    return 0;
}