Cod sursa(job #2296860)

Utilizator mirunazMiruna Zavelca mirunaz Data 5 decembrie 2018 01:31:18
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
#define M 10000010
#define MOD 666013
using namespace std;

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

void RenewMask(char *s, int n, int start, int pk, int &x)
{
    long long aux = (s[start+n] - 'a') - 1LL * (s[start] - 'a')*pk;
    while(aux < 0){
        aux += MOD;
    }
    aux = (aux +3*x)%MOD;
    x = aux;
}

bool h[MOD+5];

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

    int n, pk=1;
    in.getline(s, 22);
    n = strlen(s);
    h[CalcMask(s, n)] = true;
    while(in.getline(s, 22)) {
        h[CalcMask(s, n)] = true;
    }

    for (int i=0;i<n;++i){
        pk*=3;
    }

    int x = CalcMask(sir, n);
    while(x<0) continue;
    int ct = 0;
    if(h[x] != false) {
        ct ++;
    }

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