Cod sursa(job #2047083)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 24 octombrie 2017 15:43:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <cstring>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
char A[MAXN],B[MAXN];
char match[MAXN];
int main()
{   f>>A>>B;
    int NA=strlen(A),NB=strlen(B);
    if(NA>NB) {g<<"0\n"; g.close(); return 0;}
    int P1=1,P2=1,ha1=0,ha2=0,hb1=0,hb2=0;
    for(int i =0;i<NA;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) {P1=(P1*P)%MOD1; P2=(P2*P)%MOD2;}
    }
    int Nr = 0;
    if(hb1==ha1 && hb2==ha2) {match[0]=1; Nr++;}
    for(int i=NA;i<NB;i++)
    {   hb1=((hb1-(B[i-NA]*P1)% MOD1+MOD1)*P+B[i])%MOD1;
        hb2=((hb2-(B[i-NA]*P2)% MOD2+MOD2)*P+B[i])%MOD2;
        if(hb1==ha1 && hb2==ha2) {match[i-NA+1]=1; Nr++;}
    }
    g<<Nr<<'\n';
    Nr=0;
    for(int i=0;i<NB && Nr<1000;i++)
        if(match[i]) {Nr++; g<<i<<' ';}
    g<<'\n'; g.close(); return 0;
}