Cod sursa(job #1838089)

Utilizator tudi98Cozma Tudor tudi98 Data 30 decembrie 2016 23:38:52
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define ROF(i,a,b) for (int i = a; i >= b; i--)
#define FOREACH(it,a) for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define ld long double
#define ll long long
#define ull unsigned long long

const int base = 3;
const int modulo = 100663319;
const int MOD = 49157;

vector<int> H[MOD];

bool findHash(int x)
{
    int g = x % MOD;
    FOREACH(it,H[g])
        if (*it == x) return 1;
    return 0;
}

void addHash(int x)
{
    int g = x % MOD;
    H[g].push_back(x);
}

int main()
{
    ifstream fin("abc2.in");
    ofstream fout("abc2.out");

    string text,s;
    fin >> text;
    int len = 0;
    while (fin >> s)
    {
        len = s.size();
        int h = 0;
        FOR(i,0,len-1)
        {
            h = h * base + (s[i] - 'a');
            h = h % modulo;
        }
        if (!findHash(h)) addHash(h);
    }

    int h = 0;
    int bpower = 1;
    FOR(i,1,len-1)
        bpower = bpower * base % modulo;

    int sol = 0;
    FOR(i,0,text.size()-1)
    {
        if (i < len) {
            h = h * base + (text[i] - 'a');
            h = h % modulo;
        }
        else {
            h = h - bpower * (text[i - len] - 'a') % modulo + modulo;
            h %= modulo;
            h = h * base + (text[i] - 'a');
            h = h % modulo;
        }
        if (i >= len-1)
        {
            if (findHash(h)) sol++;
        }
    }

    fout << sol;

}