Cod sursa(job #1800518)

Utilizator Bodo171Bogdan Pop Bodo171 Data 7 noiembrie 2016 20:48:02
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<string>
using namespace std;
typedef unsigned int uint;
const uint mod=127099;
class hash_table{
    private:
        vector<uint> v[128000];
        uint idx,key;
    public:
        int finds(uint x)
        {
            key=x%mod;
            for(idx=0;idx<v[key].size();idx++)
                if(v[key][idx]==x) return 1;
            return 0;
        }
        void inserts(uint x)
        {
            if(finds(x)) return;
            key=x%mod;
            v[key].push_back(x);
        }

};
hash_table h;
string s,str;
uint x,i,j,len,p3,tot;
int main()
{
    ifstream f("abc2.in");
    ofstream g("abc2.out");
    f>>s;
    while(f>>str)
    {
        x=0;
        for(i=0;i<str.size();i++)
            x=x*3+str[i]-'a';
        h.inserts(x);
    }
    len=str.size();p3=1;
    for(i=1;i<len;i++)
        p3*=3;
    x=0;
    for(i=0;i<s.size();i++)
    {
        if(i>=len)
        {
            x-=(s[i-len]-'a')*p3;
        }
        x=x*3+s[i]-'a';
        if(i>=len-1)
        {
            tot+=h.finds(x);
        }
    }
    g<<tot;
    return 0;
}