Cod sursa(job #1790188)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 27 octombrie 2016 21:17:25
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <cstring>

const int mod1=1000003,mod2=1000007,baza=3;

using namespace std;

char sir[10000001],sir1[50001];
int v[1000010];

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    int l1,l,hash1=0,hash2=0,a1=1,a2=1,sol=0;
    gets(sir);
    l1=strlen(sir);
    while(gets(sir1))
    {
        hash1=0;hash2=0;
        l=strlen(sir1);
        for(int i=0;i<l;i++)
        {
            hash1=(hash1*baza+sir1[i])%mod1;
            hash2=(hash2*baza+sir1[i])%mod2;
        }
        v[hash1]=1;
        v[hash2]=1;
    }
    for(int i=1;i<l;i++)
    {
        a1=(a1*baza)%mod1;
        a2=(a2*baza)%mod2;
    }
    hash1=0;hash2=0;
    for(int i=0;i<l;i++)
    {
        hash1=(hash1*baza+sir[i])%mod1;
        hash2=(hash2*baza+sir[i])%mod2;
    }
    if(v[hash1]==1 && v[hash2]==1) sol++;
    for(int i=l;i<l1;i++)
    {
        hash1=((hash1-(sir[i-l]*a1)%mod1+mod1)*baza+sir[i])%mod1;
        hash2=((hash2-(sir[i-l]*a2)%mod2+mod2)*baza+sir[i])%mod2;
        if(v[hash1]==1 && v[hash2]==1) sol++;
    }
    printf("%d",sol);
    return 0;
}