Cod sursa(job #2107069)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 16 ianuarie 2018 18:44:53
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int mod = 9883;
vector <int> H[mod];
int n ,i,m,put[21];
char s[10000010];
char cuv[21];

int hashc(char v[])
{
    int val = 0,i;
    for(i=0;i<m;++i)
        val = (val * 3 + v[i] - 'a');

    return val;
}

void inserth(int x)
{
    H[x%mod].push_back(x);
}

int find_hash(int x)
{
    int key = x % mod;
    for(vector<int>::iterator it = H[key].begin();it!= H[key].end();it++)
        if((*it) == x) return 1;

    return 0;
}

int main()
{
    FILE *f = fopen("abc2.in","r");
    FILE *g = fopen("abc2.out","w");

    fscanf(f,"%s",s);
    fscanf(f,"%s",cuv);
    n = strlen(s);m = strlen(cuv);
    put[0]=1;
    for(i=1;i<=20;i++)
        put[i]=put[i-1]*3;

    inserth(hashc(cuv));

    while(fscanf(f,"%s",cuv) == 1)
    {
        inserth(hashc(cuv));
    }

    strncpy(cuv,s,m);
    int x = hashc(cuv),nr_cuv = 0;
    for(i=m;i<n;i++)
    {
        if(find_hash(x)) nr_cuv++;
        x = 3*x - (s[i-m] - 'a')*put[m] + (s[i] - 'a');
    }

    if(find_hash(x)) nr_cuv++;

    fprintf(g,"%d",nr_cuv);
}