Cod sursa(job #2296891)

Utilizator mirunazMiruna Zavelca mirunaz Data 5 decembrie 2018 02:08:56
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <bits/stdc++.h>
#define M 10000010
#define MOD 10041
using namespace std;

inline unsigned long long CalcMask(char *s, int n)
{
    unsigned long long p = 1;
    unsigned long long sum = 0;
    for(int i=n - 1; i>=0; i--) {
        sum = (s[i] - 'a')*p+sum;
        p *= 3;
    }
    return (sum);
}

inline void RenewMask(char *s, int n, int start, unsigned long long pk, unsigned long long &x)
{
    unsigned long long aux = (x - (s[start] - 'a')*pk)*3 + s[start+n]- 'a' ;
    x = aux;
}

vector<unsigned long long> h[MOD+5];

bool isIn(unsigned long long x){
    int r = x%MOD;
    for(int i = 0; i < h[r].size();++i){
        if(h[r][i] == x)
            return true;
    }
    return false;
}

int main ()
{
    ifstream in("abc2.in");
    ofstream out("abc2.out");
    char sir[M], s[22];
    in.getline(sir, M);

    int n;
    unsigned long long pk=1;
    in.getline(s, 22);
    n = strlen(s);
    h[CalcMask(s, n)%MOD].push_back(CalcMask(s,n));
    while(in.getline(s, 22)) {
        unsigned long long tmp = CalcMask(s,n);
        h[tmp%MOD].push_back(tmp);
    }

    for (int i=0;i<n;++i){
        pk*=3;
    }
    pk/=3;
    unsigned long long x = CalcMask(sir, n);
    int ct = 0;
    if(isIn(x)) {
        ct ++;
    }

    int m = strlen(sir);
    for(int i=0; i<m-n; i++) {
        RenewMask(sir, n, i, pk, x);
        if(isIn(x)) {
            ct ++;
        }
    }
    out << ct;
    return 0;
}