Cod sursa(job #1061690)

Utilizator cosmin_bobeicaCosmin Bobeica cosmin_bobeica Data 20 decembrie 2013 10:03:11
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<fstream>
#include<vector>
#include<string>
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()
{
    ifstream f("abc2.in");
    ofstream g("abc2.out");
    f>>text; lung=text.length();
    f>>cuv;  clung=cuv.length();
    unsigned int nr,afis=0,p = 1,l,j,i;
    while(!f.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);
        f>>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++;
    }
    g<<afis;
    f.close();
    g.close();
    return 0;
}