Cod sursa(job #2291891)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 28 noiembrie 2018 19:00:18
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
#define nmax 50005
#define lmax 10000005
#define kmax 22
#define mod 50013
using namespace std;

int n,m,mc,sol;
unsigned int h,t;
char s[lmax],a[kmax];
char buffer[lmax/5];


vector<unsigned int> v[mod];

void hashins(unsigned int x)
{
    v[x%mod].push_back(x);
}
int hashexist(unsigned int x)
{
    int modul=x%mod;
    for (int i=0;i<v[modul].size();i++)
        if (v[modul][i]==x)
            return 1;
    return 0;
}
int main()
{
    int i,j,x=0;
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);

    scanf("%s",&s);
    n=strlen(s);

    while (scanf("%s",&a)==1) {
        m=strlen(a);
        if (m) mc=m;
        x=0;
        for (i=0;a[i];i++)
            x=x*3+a[i]-'a';
        hashins(x);
    }
    m=mc;
    h=1;
    for (i=0;i<m;i++)
        t=1LL*t*3+s[i]-'a';
    for (i=1;i<m;i++)
        h=1LL*h*3;

    for (i=m;i<=n;i++) {
        if (hashexist(t))
            sol++;
        t=1LL*t-h*(s[i-m]-'a');
        t=1LL*t*3+s[i]-'a';
    }
    printf("%d\n",sol);

    return 0;
}