Cod sursa(job #2107048)

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

using namespace std;

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

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

    return val;
}

void inserth(int x)
{
    H.push_back(x);
}

int find_hash(int x)
{
    for(vector<int>::iterator it = H.begin();it!= H.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);
}