Cod sursa(job #2288477)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 23 noiembrie 2018 15:10:36
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define PII pair < int , int >
#define MOD 29989  
 
using namespace std;

int n, rs, len = 0;
char s[10000005], c[25];
vector < unsigned int > Hash[MOD];

unsigned int val, base = 1;

bool find(unsigned int val) {
    int search = val % MOD;

    for (auto it : Hash[search]) {
        if (it == val) return 1;
    }

    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    ifstream cin("abc2.in");
    ofstream cout("abc2.out");

    cin >> s;
    while (cin >> c) {
        len = max(len, (int)strlen(c));
        unsigned int value = 0;
        for (int j = 0; j < len; j++) {
            value = value * 3 + (c[j] - 'a');
        }

        Hash[value % MOD].push_back(value);
    }

    
    for (int i = 0; i < len; i++) {
        base *= 3;
    }

    for (int i = 0; i < strlen(s); i++) {
        val = val * 3 + (s[i] - 'a');
        
        if (i >= len) {
            val -= base * (s[i - len] - 'a');
        }

        if (i >= len - 1) {
            rs += find(val);
        }
    }

    cout << rs;

    return 0;
}