Cod sursa(job #2102442)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 8 ianuarie 2018 20:28:08
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int mod = 30000;
//unordered_map <int, bool> marcat;
vector <long long> hsh[mod + 5];
string text;
string cuv;

inline void push(long long x)
{
    int p = x % mod;
    hsh[p].push_back(x);
}

inline bool searchfor(long long x)
{
    int p = x % mod;
    for(auto it : hsh[p])
        if(it == x)
            return 1;
    return 0;
}

void codif(string s)
{
    /*
    int p1 = 0;
    int p2 = 0;

    for(auto it : s)
    {
        p1 = (p1 * 3 + it - 'a') % mod1;
        p2 = (p2 * 3 + it - 'a') % mod2;
    }
    */
    //marcat[make_pair(p1, p2)] = 1;
    long long p = 0;
    for(auto it : s)
        p = p * 3 + it - 'a';
    push(p);
}

int main()
{
    in >> text;
    while(in >> cuv)
        codif(cuv);
    int lg = cuv.size();
    long long put3 = 1;
    long long a = 0;
    for(int i = 0; i < lg; i++)
    {
        a = a * 3 + text[i] - 'a';
        if(i != 0)
            put3 = put3 * 3;
    }
    int nr = 0;
    for(register unsigned int i = lg; i < text.size(); i++)
    {
        if(searchfor(a) == 1)
            nr++;
        a = a - put3 * (text[i - lg] - 'a');
        a = a * 3 + text[i] - 'a';
    }
    if(searchfor(a) == 1)
        nr++;
    out << nr << "\n";
    return 0;
}