Cod sursa(job #1110040)

Utilizator cat_red20Vasile Ioana cat_red20 Data 17 februarie 2014 19:54:28
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<fstream>
#include<string.h>
#define MOD 30011
#include<vector>
using namespace std;

int l,n,sol;
char s[10000001],t[21];
vector<unsigned int>h[MOD];
ifstream fin("abc2.in");
ofstream fout("abc2.out");

void citire()
{
    unsigned int x;
    fin>>s;

    while(fin>>t)
    {
        l=strlen(t);
        x=0;
        for(int i=0;i<l;i++)
        {
            x=x*3+t[i]-'a';
        }
        h[x%MOD].push_back(x);
    }
}

int cauta(unsigned int x)
{
    for(int i=0;i<h[x%MOD].size();i++)
    {
        if(h[x%MOD][i]==x)
        return 1;
    }
    return 0;
}

void solutie()
{
    unsigned int x=0,p=1;
    int len;
    len=strlen(s);
    for(int i=0;i<l;i++)
    {
        x=x*3+s[i]-'a';
        p=p*3;
    }
    p=p/3;
    sol+=cauta(x);
    for(int i=l;i<len;i++)
    {
        x-=(s[i-l]-'a')*p;
        x=x*3+s[i]-'a';
        sol+=cauta(x);
    }
}

int main()
{
    citire();
    solutie();
    fout<<sol;
    return 0;
}