Cod sursa(job #3209100)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 1 martie 2024 21:09:36
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>
#define int unsigned int
#define DIM 1000001
#define BASE 666013

using namespace std;

ifstream fin("ahocorasick.in");

ofstream fout("ahocorasick.out");

/*
char s[DIM], a[DIM], answer[DIM];
*/

string s, a, answer;

int power[DIM], _hash[DIM];

int ap[201], ap2[201 * 201];

int n, i, ret, new_hash, Max, Q;

vector <int> event[100001];

void build_hash(){

    power[0] = 1;

    for(i=1;i<=s.size();i++)

        power[i] = (power[i - 1] * BASE);

    _hash[2] = s[0];

    for(i=2;i<=s.size();i++)

        _hash[i + 1] = (_hash[i] * BASE + s[i - 1]);

}

int get_hash(int st, int dr){

    int answer = (_hash[dr + 1] - _hash[st] * power[dr - st + 1]);

    return answer;

}

int32_t main(){

    fin >> s;

    build_hash();

    for(i=0;i<s.size() - 2;i++){

        int aux = (s[i] * 4) + s[i + 1] * 2 + s[i + 2];

        event[aux].push_back(i + 1);

        ap[s[i]] += 1;

        aux = s[i] * 100 + s[i + 1];

        ap2[aux]++;

    }

    ap[s[s.size() - 1]]++;

    ap[s[s.size() - 2]]++;

	int aux = s[s.size() - 2] * 100 + s[s.size() - 1];

    ap2[aux]++;

    fin >> Q;

    while(Q--){

        fin >> a;

        new_hash = 0;

        ret = 0;

        for(i=0;i<a.size();i++)

            new_hash = (new_hash * BASE + a[i]);

        if(a.size() == 1){

            ret = ap[a[0]];

        }

        else if(a.size() == 2){

			int aux = a[0] * 100 + a[1];

            ret = ap2[aux];

        }

        else {

            int aux = a[0] * 4 + a[1] * 2 + a[2];

            for(auto k : event[aux]){

				if(k + a.size() - 1 > s.size())

					break;

                if(get_hash(k, k + a.size() - 1) == new_hash){

                    ++ret;

                }

            }


        }

        fout << ret << "\n";



    }



}