Cod sursa(job #1493568)

Utilizator GinguIonutGinguIonut GinguIonut Data 29 septembrie 2015 17:24:33
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <vector>
#define cMax 10000005
#define MOD 1000001
#define cuvMax 22
#include <string.h>
#define CH *s-'a'
using namespace std;
char line[cMax], cuv[cuvMax];
int i, m;
unsigned int sol, tot, div, n, val;
vector <unsigned int> G[MOD];
int search_value(unsigned int val)
{
    int list=val%MOD;
    for(vector<unsigned int>::iterator it=G[list].begin();it!=G[list].end();it++)
        if(*it==val)
            return 1;
    return 0;
}
int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    scanf("%s", &line);
    int nmax;
    while(scanf("%s", &cuv)==1)
    {
        n=strlen(cuv);
        if(n)
            nmax=n;
        val=0;
        for(i=0;cuv[i];i++)
            val=1ll*val*3+cuv[i]-'a';
        if(!search_value(val))
            G[val%MOD].push_back(val);
    }
    n=nmax;
    m=strlen(line);
    for(i=0;i<n;i++)
        tot=tot*3+line[i]-'a';
    div=1;
    for(i=1;i<n;i++)
        div=1ll*div*3;
    for(i=n;i<=m;i++)
    {
        sol+=search_value(tot);
        tot=1ll*tot-div*(line[i-n]-'a');
        tot=1ll*tot*3+line[i]-'a';
    }
    printf("%d", sol);
    return 0;
}