Cod sursa(job #519823)

Utilizator S7012MYPetru Trimbitas S7012MY Data 6 ianuarie 2011 18:12:54
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>
#define DN 50005
using namespace std;

typedef set<int>::iterator it;

int hash(string a) {
    int r=0;
    for(int i=0; i<=a.size(); ++i) r=r*3+a[i]-'a';
    return r;
}

int main()
{

    string sir, cuv,caut;
    set<int> s;
    ifstream f("abc2.in");
    ofstream g("abc2.out");
    int sol=0;
    getline(f,sir);
    int si=hash(sir);//sirul
    int sz,n=sir.size();
    for(;0==f.eof();) if(f.good()) {
        getline(f,cuv);
        if(0==cuv.empty()) {
            sz=cuv.size();
            s.insert(hash(cuv));
        }
    }
    int pow=1;
    it c;
    for (int i=1; i<sz; ++i) pow*=3;
    for(int i=sz; i<n; ++i) {
        si-=pow*(sir[i-sz]-'a');
        si=si*3+sir[i]-'a';
        c=s.find(si);
        if(c!=s.end()) ++sol;
    }
    g<<sol;
    return 0;
}