Cod sursa(job #2369136)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 5 martie 2019 21:22:00
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>



using namespace std;



ifstream fin("abc2.in");

ofstream fout("abc2.out");



const int NMAX = 10000005;

const int MOD = 10007;



vector <long long> v[MOD+5];

char a[NMAX];

char c[25];



bool caut(long long x)

{

    int aux=x%MOD;

    for(int i=0;i<v[aux].size();i++) if(v[aux][i]==x) return 1;

    return 0;

}



void hash_insert(long long x)

{

    int aux=x%MOD;

    if(caut(aux)==0)

    {

        v[aux].push_back(x);

    }

}



int main()

{

    fin >> (a+1);

    int asize=strlen(a+1);

    int n,baza;

    while(!fin.eof())

    {

        fin >> (c+1);

        n=strlen(c+1);

        baza=3;

        long long nr=0;

        for(int i=1;i<=n;i++) nr=nr*baza+(c[i]-'a'+1);

        hash_insert(nr);

    }

    long long putere=1;

    long long nr=0;

    for(int i=1;i<=n;i++)

    {

        nr=nr*baza+(a[i]-'a'+1);

        putere*=baza;

    }

    putere/=baza;

    int rasp=0;

    if(caut(nr)==1) rasp++;

    for(int i=n+1;i<=asize;i++)

    {

        nr-=putere*(a[i-n]-'a'+1);

        nr*=baza;

        nr+=a[i]-'a'+1;

        if(caut(nr)==1) rasp++;

    }

    fout << rasp;

    return 0;

}