Cod sursa(job #1782919)

Utilizator mantisVraciu Stefan mantis Data 18 octombrie 2016 17:12:36
Problema Abc2 Scor 100
Compilator cpp Status done
Runda hash_excelenta Marime 1.09 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 1000003
using namespace std;

ifstream f("abc2.in");
ofstream g("abc2.out");

unsigned int a,n,m,nr,p3[25];
char Cuvant[25],S[10000005];
vector<unsigned int> H[MOD+3];

void GenerarePuteri()
{
    p3[1]=1;
    for(int i=2;i<=21;i++) p3[i]=p3[i-1]*3;
}

bool CautCuvant(unsigned int a)
{
     vector<unsigned int>::iterator it=H[a%MOD].begin(), sf=H[a%MOD].end();
        bool w=true;
        for(;it!=sf && w;it++)
            if((*it)==a)  return true;
        return false;
}

int main()
{
    f>>(S+1);
    GenerarePuteri();
    while(f>>(Cuvant+1))
    {
        n=strlen(Cuvant+1);
        a=0;
        for(int i=1;i<=n;i++) a=a+p3[i]*(Cuvant[i]-97);
        if(!CautCuvant(a))
            H[a%MOD].push_back(a);
    }
    a=0;
    for(int i=1;i<=n;i++) a=a+p3[i]*(S[i]-97);
    if(CautCuvant(a)) nr++;
    m=strlen(S+1);
    for(int i=n+1;i<=m;i++)
    {
        a/=3;
        a=a+p3[n]*(S[i]-97);
        if(CautCuvant(a)) nr++;
    }
    g<<nr<<'\n';
    g.close();
    return 0;
}