Cod sursa(job #2636780)

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

using namespace std;

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

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

bool fr[MOD];

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 = (1LL * val * base % MOD + (cuv[ i ] - 'a')) % MOD;
        }

        fr[ val ] = 1;
    }

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

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

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

    if (fr[ val ]) ++ sol;

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

        if (fr[ val ])
            ++ sol;
    }

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

int main()
{
    Read ();

    Solve ();

    return 0;
}