Cod sursa(job #2167111)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 13 martie 2018 20:14:35
Problema Aho-Corasick Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 2.81 kb
#include <bits/stdc++.h>

using namespace std;
#define ll long long

const int N = 1e6 + 5;
const int MOD1 = 1e9 + 7;
const int BASE1 = 71;
const int MOD2 = 1e9 + 9;
const int BASE2 = 101;

char A[N];
char buffer[N];
pair<int, int> queryHash[105];
int sz[105];
pair <int, int> h[N];
pair <int, int> inv[N];

int lgpow(int b, int e, int m){
    int sol = 1;
    while(e){
        if(e & 1){
            sol = (1LL * sol * b)%m;
        }
        b = (1LL * b * b)%m;
        e >>= 1;
    }
    return sol;
}

struct Hash{
    pair <int, int> getHash(char *s){
        int n = strlen(s + 1);
        pair <int, int> ret = {0, 0};
        int p1 = 1;
        int p2 = 1;
        for(int i = 1;i <= n;i++){
            ret.first = (0LL + ret.first + 1LL * p1 * (s[i] - 'a' + 1))%MOD1;
            ret.second = (0LL + ret.second + 1LL * p2 * (s[i] - 'a' + 1))%MOD2;
            p1 = (1LL * p1 * BASE1)%MOD1;
            p2 = (1LL * p2 * BASE2)%MOD2;
        }
        return ret;
    }
};

pair <int, int> getSubHash(int i, int l){
    pair <int, int> ret = {(h[i].first - h[i - l].first + MOD1)%MOD1, (h[i].second - h[i - l].second + MOD2)%MOD2};
    ret.first = (1LL * ret.first * inv[i - l].first)%MOD1;
    ret.second = (1LL * ret.second * inv[i - l].second)%MOD2;
    return ret;
}

vector <pair<int, int>> hashes[10005];
vector <int> toSearch;
bool usedL[10005];

int main(){
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
    Hash HashClass;
    scanf("%s", A + 1);
    int l = strlen(A + 1);
    int IB1 = lgpow(BASE1, MOD1 - 2, MOD1);
    int IB2 = lgpow(BASE2, MOD2 - 2, MOD2);
    inv[0] = {1, 1};
    int p1, p2;
    p1 = p2 = 1;
    for(int i = 1;i <= l;i++){
        inv[i].first = (1LL * inv[i - 1].first * IB1)%MOD1;
        inv[i].second = (1LL * inv[i - 1].second * IB2)%MOD2;
        h[i].first = (0LL + h[i - 1].first + 1LL * p1 * (A[i] - 'a' + 1))%MOD1;
        h[i].second = (0LL + h[i - 1].second + 1LL * p2 * (A[i] - 'a' + 1))%MOD2;
        p1 = (1LL * p1 * BASE1)%MOD1;
        p2 = (1LL * p2 * BASE2)%MOD2;
    }
    int n;
    scanf("%d", &n);
    for(int i = 1;i <= n;i++){
        scanf("%s", buffer + 1);
        queryHash[i] = HashClass.getHash(buffer);
        sz[i] = strlen(buffer + 1);
        if(usedL[sz[i]] == false)
            toSearch.emplace_back(sz[i]);
            usedL[sz[i]] = true;
    }
    for(auto &it : toSearch){
        for(int i = it;i <= l;i++){
            hashes[it].emplace_back(getSubHash(i, it));
        }
        sort(hashes[it].begin(), hashes[it].end());
    }
    for(int i = 1;i <= n;i++){
        printf("%d\n", upper_bound(hashes[sz[i]].begin(), hashes[sz[i]].end(), queryHash[i]) - lower_bound(hashes[sz[i]].begin(), hashes[sz[i]].end(), queryHash[i]));
    }
    return 0;
}