Cod sursa(job #1683902)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 10 aprilie 2016 17:17:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<string.h>
using namespace std;
#define P 73
#define MOD1 100007
#define MOD2 100021
#define Nmax 2000007
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int P1=1,P2=1,LA,LB,nr=0;
bool Match[Nmax];
char A[Nmax],B[Nmax];
int main()
{
    f>>A>>B;
    LA=strlen(A);
    LB=strlen(B);
    if(LA>LB)
    {
        g<<"0"<<'\n';
        return 0;
    }
    int HA1=0,HA2=0,HB1=0,HB2=0;
    ///calculam cele doua functii Hash pentru sirul A si pentru prima portiune de lungime LA din B
    for(int i=0;i<LA;++i)
    {
        HA1=(HA1*P+A[i])%MOD1;
        HA2=(HA2*P+A[i])%MOD2;

        HB1=(HB1*P+B[i])%MOD1;
        HB2=(HB2*P+B[i])%MOD2;

        if(i>=1) P1=(P1*P)%MOD1,P2=(P2*P)%MOD2;
    }
    if(HA1==HB1&&HA2==HB2) nr++,Match[0]=1;
    for(int i=LA;i<LB;i++)
    {
        HB1=((HB1-(B[i-LA]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
        HB2=((HB2-(B[i-LA]*P2)%MOD2+MOD2)*P+B[i])%MOD2;
        if(HA1==HB1&&HA2==HB2) nr++,Match[i-LA+1]=1;
    }
    g<<nr<<'\n';
    nr=0;
    for(int i=0;i<LB&&nr<1000;++i)
        if(Match[i]) nr++, g<<i<<" ";
    g<<'\n';
    return 0;
}