Cod sursa(job #2636783)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 19 iulie 2020 21:56:43
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f ("abc2.in");
ofstream g ("abc2.out");

constexpr int base = 3;
constexpr int MOD = 666013;

vector <unsigned int> fr[MOD];

unsigned int length, power;

string text;

void Read () {
    f >> text;

    string cuv;

    while (f >> cuv) {
        int val = 0;

        length = cuv.size();

        for (int i = 0; i < cuv.size(); ++ i ) {
            val = val * base + (cuv[ i ] - 'a');
        }

        fr[ val % MOD ].push_back(val);
    }

    power = 1;
    for (int i = 1; i < length; ++ i ) {
        power = power * base;
    }
}

bool Verif (unsigned int val) {
    for (int i = 0; i < fr[val % MOD].size(); ++ i ) {
        if (fr[val % MOD][i] == val) return 1;
    }

    return 0;
}

void Solve () {
    unsigned int val = 0;
    int sol = 0;

    for (int i = 0; i < length; ++ i ) {
        val = val * base + (text[ i ] - 'a');
    }

    if (Verif(val)) ++ sol;

    for (int i = length; i < text.size(); ++ i ) {
        val = (val - power * (text[ i - length ] - 'a')) * base + (text[ i ] - 'a');

        if (Verif(val))
            ++ sol;
    }

    g << sol << '\n';
}

int main()
{
    Read ();

    Solve ();

    return 0;
}