Cod sursa(job #2768652)

Utilizator DragosC1Dragos DragosC1 Data 11 august 2021 18:03:20
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
string s, aux;
unsigned int base;
int l, l2;
const int MOD = 10003;
	
vector <unsigned int> mp[MOD];
inline bool exista(unsigned int x) {
    unsigned int key = x % MOD;
    for (int i = 0; i < mp[key].size(); ++i)
        if (mp[key][i] == x ) return 1;
    return 0;
}

inline void push(unsigned int x){
    if (!exista(x)) {
        unsigned int key = x % MOD;
        mp[key].push_back(x);
    }
}

void read() {
    int i, j;
    unsigned int hash;
    ifstream f("abc2.in");
    f >> s;
    while (f >> aux) {
        hash = 0;
        base = 1;
        for (j = 0; j < aux.size(); j++) 
            hash = hash * 3 + (aux[j] - 'a');
        l2 = aux.size();
        push(hash);
    }
}
 
int nr;
 
void solve() {
    int i;
 
    unsigned int hash = 0;
    for (i = 0; i < l2; i++) {
        hash = hash * 3 + (s[i] - 'a');
        base = base * 3;
    }
    base /= 3;
    if (exista(hash))
        nr++;
 
    for (i = l2; i < s.size(); i++) {
        hash = (hash - (s[i - l2] - 'a') * base) * 3 + (s[i] - 'a');
        if (exista(hash))
            nr++;
    }
}
 
void output() {
    ofstream g("abc2.out");
    g << nr;
    g.close();
}
 
int main() {
    read();
    solve();
    output();
    return 0;
}