Cod sursa(job #2636784)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 19 iulie 2020 22:11:50
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <vector>

using namespace std;

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

constexpr int base = 3;
constexpr int MOD = 666013;
constexpr int cuvmax = 5e4 + 5;

unsigned int rest[cuvmax], ultpoz[cuvmax], value[cuvmax];

unsigned int ult[MOD];

unsigned int length, power;

string text;

void Read () {
    f >> text;

    string cuv;

    unsigned int N = 0;

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

        length = cuv.size();

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

        value[ ++ N ] = val;
        rest[ N ] = val % MOD;

        if (ult[ val % MOD ])
            ultpoz[ N ] = ult[ val % MOD ];

        ult[ val % MOD ] = N;
    }

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

bool Verif (unsigned int val) {
    for (int i = ult[ val % MOD ]; i != 0; i = ultpoz[ i ]) {
        if (val == value[ i ]) 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;
}