Cod sursa(job #1060368)

Utilizator thewildnathNathan Wildenberg thewildnath Data 17 decembrie 2013 22:05:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

#define MOD 99991

char a[10000010],aux[25];
vector<long long> v[MOD+10];

inline bool find(int h)
{
    int list=h%MOD;
    vector<long long>::iterator it;
    for(it=v[list].begin();it!=v[list].end();++it)
        if(*it==h)
            return 1;
    return 0;
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    long long n,l=0,i,sol=0,h,p;

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

    while(scanf("%s\n",&aux)!=EOF)
    {
        l=strlen(aux);
        h=0;
        for(i=0;i<l;++i)
            h=h*3+aux[i];

        if(!find(h))
            v[h%MOD].push_back(h);
    }

    p=1;h=0;
    for(i=1;i<l;++i)
        p*=3;
    for(i=0;i<l;++i)
        h=h*3+a[i];
    sol+=find(h);

    for(;i<n;++i)
    {
        h-=p*a[i-l];
        h=h*3+a[i];
        sol+=find(h);
    }

    printf("%d\n",sol);

    return 0;
}