Cod sursa(job #2189630)

Utilizator alexradu04Radu Alexandru alexradu04 Data 28 martie 2018 19:09:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <stdio.h>
#include <string.h>
 
#define NMAX 2000001
#define p 29
#define MOD1 120997
#define MOD2 121271
 
char a[NMAX], b[NMAX];
int na, nb;
int hasha1, hasha2, p1, p2;
char match[NMAX];
int main()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    gets(a);
    gets(b);
    na=strlen(a);
    nb=strlen(b);
    p1=p2=1;
    hasha1=hasha2=0;
    for(int 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;
        }
    }
    
    int hash1=0,hash2=0;
    for(int i=0;i<na;i++)
        {hash1=(hash1*p+b[i])%MOD1;hash2=(hash2*p+b[i])%MOD2;}
    int nr=0;
    if(hash1==hasha1&&hash2==hasha2)
        {match[0]=1;nr++;}
    for(int i=na;i<nb;i++)
    {
        hash1=((hash1-(b[i-na]*p1)%MOD1+MOD1)*p+b[i])%MOD1;
        hash2=((hash2-(b[i-na]*p2)%MOD2+MOD2)*p+b[i])%MOD2;
        if(hash1==hasha1&&hash2==hasha2)
            {match[i-na+1]=1;nr++;}
    }
    printf("%d\n",nr);
    nr=0;
    for(int i=0;i<nb&&nr<1000;i++)
        if(match[i])
            {nr++;printf("%d ",i);}
    printf("\n");
    return 0;
}