Cod sursa(job #3267589)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 11 ianuarie 2025 14:51:43
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <bits/stdc++.h>
using namespace std;

const int p = 3, MOD = (1 << 17) - 1;
vector<unsigned int> m[MOD];

bool searchHash(unsigned int k) {
    unsigned int r = k & MOD;
    for (int i = 0; i < (int)m[r].size(); ++i) {
        if (m[r][i] == k) {
            return 1;
        }
    }
    return 0;
}

void insertHash(unsigned int k) {
    unsigned int r = k & MOD;
    if (!searchHash(k)) {
         m[r].push_back(k);
    }
}

unsigned int hashF(string word) {
    unsigned int res = 0;
    for (int i = 0; i < (int)word.size(); ++i) {
        res = res * p + (word[i] - 'a');
    }
    return res;
}

unsigned int calcPow(int base, int power) {
    unsigned int res = 1;
    for (int i = 1; i <= power; ++i) {
        res *= base;
    }
    return res;
}

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

    int wSize;

    int buffSize = 1e5;
    char buffer[buffSize + 1];
    bool firstLineEnded = 0;
    string text = "";
    while(cin) {
        cin.read(buffer, buffSize);
        int buffLength = cin.gcount();
        for(int i = 0; i < buffLength; ++i) {
            if(!firstLineEnded) {
                if(buffer[i] == '\n') {
                    firstLineEnded = 1;
                }
            } else {
                if(buffer[i] == '\n') {
                    insertHash(hashF(text));
                    wSize = text.size();
                    text = "";
                }
                else {
                    text += buffer[i];
                }
            }
        }
    }
    cin.close();
    ifstream ffin("abc2.in");
    unsigned int res = 0, ans = 0;
    unsigned int last = calcPow(3, wSize - 1);
    text = "";
    bool ok = 0;
    deque<int> D;
    while(ffin) {
        ffin.read(buffer, buffSize);
        int buffLength = ffin.gcount();
        for (int i = 0; i < buffLength; ++i) {
            if(buffer[i] == '\n') {
                cout << ans;
                return 0;
            }
            int c = buffer[i] - 'a';
            res = res * p + c;
            D.push_back(c);
            if(i >= wSize - 1) ok = 1;
            if (ok) {
                if (searchHash(res)) {
                    ++ans;
                }

                res = res - last * D[0];
                D.pop_front();
            }
        }
    }
}