Cod sursa(job #1675259)

Utilizator alexburdescuBurdescu Alexandru alexburdescu Data 5 aprilie 2016 10:51:44
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<iostream>
#include<cstring>
#include<fstream>
using namespace std;
char poz[2000000];
int hashA1,hashA2,P1,P2,NA,NB,hashB1,hashB2,nr;
char A[2000009],B[2000009];
#define MOD1 100007
#define MOD2 100021
#define P 73
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
int main ()
{
    fin.get(A,2000009);
    fin.get();
    fin.get(B,2000009);
    NA=strlen(A);
    NB=strlen(B);
    if(NA>NB)
    {
        fout<<"0";
        return 0;
    }

    P1=1;
    P2=1;
    hashA1=hashA2=hashB1=hashB2=0;
    int i;
    for(i=0;i<NA;i++)
    {
        hashA1=(hashA1*P+A[i])%MOD1;
        hashA2=(hashA2*P+A[i])%MOD2;
        if(i!=0)
        {
            P1=(P1*P)%MOD1;
            P2=(P2*P)%MOD2;
        }
    }
    for(i=0;i<NA;i++)
    {
        hashB1=(hashB1*P+B[i])%MOD1;
        hashB2=(hashB2*P+B[i])%MOD2;
        if(hashA1==hashB1 && hashA2==hashB1)
        {
            nr++;
            poz[0]=1;
        }
    }
    for(i=NA;i<NB;i++)
    {
        hashB1=((hashB1- (P1 * B[i-NA]) %MOD1 +MOD1) *P+ B[i])%MOD1;
        hashB2=((hashB2- (P2 * B[i-NA]) %MOD2 +MOD2) *P+ B[i])%MOD2;
        if(hashA1==hashB1 && hashA2==hashB2)
        {
            nr++;
            poz[i-NA+1]++;
        }
    }
    fout<<nr<<endl;
    int x=0;
    for(i=1; i<NB && x<1000 ; i++)
    {
        if(poz[i])
        {
            fout<<i<<" ";
            x++;
        }
    }
    fin.close();
    fout.close();
    return 0;
}