Cod sursa(job #1969208)

Utilizator raduzxstefanescu radu raduzx Data 18 aprilie 2017 12:36:37
Problema Potrivirea sirurilor Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define nmax 2000010
#define p 101
#define mod1 107
#define mod2 103
char a[nmax],b[nmax];
int Ahash1,Ahash2,Bhash1,Bhash2,poz[1002],cate,pmax1,pmax2;
int main()
{
    int nra,nrb,i;
    f>>a;
    f>>b;
    nra=strlen(a)-1;
    pmax1=pmax2=1;
    for(i=0;i<=nra;i++)
    {
        Ahash1=(Ahash1*p+a[i])%mod1;
        Ahash2=(Ahash2*p+a[i])%mod2;
        if(i)
        {pmax1*=p;
        pmax1%=mod1;
        pmax2*=p;
        pmax2%=mod2;}

    }
    nrb=strlen(b)-1;
    if(nrb<nra)
        g<<"0";
    else
    {
        for(i=0;i<=nra;i++)
        {
            Bhash1=(Bhash1*p+b[i])%mod1;
            Bhash2=(Bhash2*p+b[i])%mod2;
        }
        if(Bhash1==Ahash1 and Bhash2==Ahash2)
        {
            cate+=1;
            poz[cate]=0;
        }
        int ok=0;
        for(i=nra+1;i<=nrb;i++)
        {
            if(i==7)
                ok=1;
            Bhash1-=(pmax1*(b[i-nra-1]))%mod1;
            if(Bhash1<0)
                Bhash1+=mod1;
            Bhash1=(Bhash1*p+b[i])%mod1;


            Bhash2-=(pmax2*(b[i-nra-1]))%mod2;
            if(Bhash2<0)
                Bhash2+=mod2;
            Bhash2=(Bhash2*p+b[i])%mod2;


            if(Bhash1==Ahash1 and Bhash2==Ahash2)
            {
                cate+=1;
                if(cate<=1000)
                    poz[cate]=i-nra;
            }
        }
        g<<cate<<'\n';
        cate=min(cate,1000);
        for(i=1;i<=cate;i++)
        g<<poz[i]<<" ";
    }

    return 0;
}