Cod sursa(job #2065306)

Utilizator alexandruilieAlex Ilie alexandruilie Data 13 noiembrie 2017 18:09:46
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <string.h>
#define mod1 100007
#define mod2 100021
#define p 73
using namespace std;
int hash1,hash2,hash3,hash4,lg1,lg2,i,nr,v[1001],k,p1=1,p2=1;
char a[2000001],b[2000001];
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
    f>>a>>b;
    lg1=strlen(a);
    lg2=strlen(b);
    if(lg1>lg2) g<<0;
    else{
    for(i=0;i<lg1;i++)
    {
        hash1=(hash1*p+a[i])%mod1;
        hash2=(hash2*p+a[i])%mod2;
        if(i)
        {
            p1=(p1*p)%mod1;
            p2=(p2*p)%mod2;
        }
        hash3=(hash3*p+b[i])%mod1;
        hash4=(hash4*p+b[i])%mod2;
    }
    if(hash1==hash3&&hash2==hash4)
        nr++,v[++k]=1;
    for(i=lg1;i<lg2;i++)
    {
       hash3=((hash3-(b[i-lg1]*p1)%mod1+mod1)*p+b[i])%mod1;
       hash4=((hash4-(b[i-lg1]*p2)%mod2+mod2)*p+b[i])%mod2;
        if(hash3==hash1&&hash4==hash2)
            {nr++;
        if(k<1000) v[++k]=i-lg1+1;}
    }
    g<<nr<<'\n';
    for(i=1;i<=k;i++) g<<v[i]<<' ';
    }
    return 0;
}