Cod sursa(job #1061688)

Utilizator cosmin_bobeicaCosmin Bobeica cosmin_bobeica Data 20 decembrie 2013 09:57:25
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
using namespace std;

const int MOD=99991;
typedef vector<unsigned int> hesh;
typedef hesh::iterator hit;
hesh ht[MOD+1];
unsigned int lung, clung;
string text,cuv;

inline bool find(unsigned x)
{
    for(hit i=ht[x%MOD].begin() ; i!=ht[x%MOD].end() ; i++)
        if(x==*i)
            return 1;
    return 0;
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    cin>>text;
    lung=text.length();
    cin>>cuv;
    clung=cuv.length();
    unsigned int nr,afis=0,p = 1,l,j,i;
    while(!cin.eof())
    {
        nr=0;
        for(int i=0; i<clung; i++)
            nr=nr*3+cuv[i]-'a';
        if(!find(nr))
            ht[nr%MOD].push_back(nr);
        cin>>cuv;
    }
    for(int i = 1; i < clung; i++)
        p *= 3;
    l=0;
    for(int i=0; i<clung; i++)
        l=l*3+text[i]-'a';
    if (find(l)) afis++;
    for(int i=clung; i<lung; i++)
    {
        l-=(text[i-clung]-'a')*p;
        l=(text[i]-'a')+3*l;
        if(find(l))
            afis++;
    }
    cout<<afis;
    return 0;
}