Cod sursa(job #2291852)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 28 noiembrie 2018 18:24:19
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#define MOD 30011
using namespace std;
vector <unsigned int> h[MOD];
inline int M(unsigned int x)
{
    if(x < MOD)
        return x;
    return x%MOD;
}
inline unsigned int val(string S,int dim)
{
    unsigned int x = 0, p3 = 1;
    for (int i = dim - 1; i > -1; --i)
    {
        x += (S[i] - 'a') * p3;
        p3 *= 3;
    }
    return x;
}
inline void Push(unsigned int x)
{
    int p = M(x);
    for (int i = 0; i < h[p].size(); ++i)
        if(h[p][i] == x)
        return;
    h[p].push_back(x);
}
inline bool Search(unsigned int x)
{
    int p = M(x);
    for (int i = 0; i < h[p].size(); ++i)
        if(h[p][i] == x)
        return true;
    return false;
}
int main()
{
    ifstream fin ("abc2.in");
    ofstream fout ("abc2.out");
    string s,curr;
    int i,n,k,cnt = 0;
    unsigned x,P = 1;
    fin >> s >> curr;
    k = curr.size();
    n = s.size();
    for (i = 1; i < k; ++i)
        P *=3;
    x = val(curr,k);
    Push(x);
    while(fin >> curr)
    {
        x = val(curr,k);
        Push(x);
    }
    x = val(s,k);
    if(Search(x))
        ++cnt;
    for(i = k; i < n; ++i)
    {
        x -= (s[i - k] - 'a') * P;
        x = x * 3 + s[i] - 'a';
        if(Search(x))
            ++cnt;
    }
    fout << cnt;
    return 0;
}