Cod sursa(job #2096286)

Utilizator mihailrazMihail Turcan mihailraz Data 28 decembrie 2017 22:10:27
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>
#define LMAX 2000000
#define BAZA 75
#define MOD1 100007
#define MOD2 100021

using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int nrap,val1,val2,rhash1,rhash2,lgt,lgp,putere=1;
char A[LMAX+1],B[LMAX+1];
vector <int> V;

void Rabin_Karp(char T[], char P[])
{
    lgt=strlen(T);
    lgp=strlen(P);
    for(int i=1; i<=lgp-1; i++)
    {
        putere*=BAZA;
        putere%=MOD1;
        putere%=MOD2;
    }
    for(int i=0; i<lgp; i++)
    {
        val1=(val1*BAZA%MOD1%MOD2+(P[i]-'0'))%MOD1%MOD2;
        val2=(val2*BAZA%MOD1%MOD2+(P[i]-'0'))%MOD1%MOD2;
    }
    ///fo<<val<<"\n";
    for(int i=0; i<lgp; i++)
    {
        rhash1=(rhash1*BAZA%MOD1/*%MOD2*/+(T[i]-'0'))%MOD1/*%MOD2*/;
        rhash2=(rhash2*BAZA%MOD2/*%MOD2*/+(T[i]-'0'))%MOD2/*%MOD2*/;
    }
    ///fo<<rhash<<"\n";
    if(rhash1==val1 && rhash2==val2)
    {
        nrap++;
        V.push_back(0);
    }
    for(int i=lgp; i<lgt; i++)
    {
        rhash1=(((rhash1-putere*(T[i-lgp]-'0'))%MOD1+MOD1)*BAZA+(T[i]-'0'))%MOD1;
        rhash2=(((rhash2-putere*(T[i-lgp]-'0'))%MOD1+MOD1)*BAZA+(T[i]-'0'))%MOD1;
        ///rhash=(((rhash-putere*(T[i-lgp]-'0'))%MOD2+MOD2)*BAZA+(T[i]-'0'))%MOD2;
        if(rhash1==val1 && rhash2==val2 && nrap<1000)
        {
            nrap++;
            V.push_back(i-lgp+1);
        }
        ///fo<<rhash<<"\n";
    }
}

void afisare(void)
{
    fo<<nrap<<"\n";
    for(int i=0; i<V.size(); i++)
        fo<<V[i]<<" ";
}

int main()
{
    fi>>A;
    fi>>B;
    Rabin_Karp(B,A);
    afisare();
    fi.close();
    fo.close();
    return 0;
}