Cod sursa(job #2469086)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 6 octombrie 2019 15:07:12
Problema Aho-Corasick Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int MAX_SIZE = 1e6 + 100;
const int VOCAB = 26;
const int MAX_N = 100;
const int CUV_SIZE = 1e4 + 10;

int f[MAX_SIZE][VOCAB];
int fail[MAX_SIZE];
int p[MAX_SIZE];
int lch[MAX_SIZE];
int cnt[MAX_SIZE];

int next_id = 2;

char s[MAX_SIZE], cuv[CUV_SIZE];
int ix[MAX_N];

void calc_fail(int n) {
//    cout << n << ' ' << fail[n] << endl;
    for (int i = 0; i < VOCAB; i++)
        if (f[n][i]) {
            int u = f[n][i];
            int suf = fail[n];
            while (suf != 1 && !f[suf][i])
                suf = fail[suf];
            if (f[suf][i] && f[suf][i] != u)
                suf = f[suf][i];
            else
                suf = 1;
            fail[u] = suf;
            calc_fail(u);
        }
}

int main() {
    ifstream cin("ahocorasick.in");
    ofstream cout("ahocorasick.out");

    int n;
    cin >> s;
    cin >> n;

//    cout << "1: " << endl;

    for (int n0 = 0; n0 < n; n0++) {
        cin >> cuv;
        int i = 1;
        for (int pos = 0; cuv[pos]; pos++) {
            if (!f[i][cuv[pos] - 'a']) {
//                cout << next_id << ": ";
//                for (int j = 0; j <= pos; j++)
//                    cout << cuv[j];
//                cout << endl;
                p[next_id] = i;
                f[i][cuv[pos] - 'a'] = next_id++;
            }
            i = f[i][cuv[pos] - 'a'];
            lch[i] = cuv[pos] - 'a';
        }
        ix[n0] = i;
    }

    fail[1] = 1;
    calc_fail(1);

    int i = 1;
    for (int pos = 0; s[pos]; pos++) {
        while (i != 1 && !f[i][s[pos] - 'a'])
            i = fail[i];
        if (f[i][s[pos] - 'a'])
            i = f[i][s[pos] - 'a'];
        cnt[i]++;
    }

//    for (int i = 1; i < next_id; i++)
//        cout << i << " -fail-> " << fail[i] << endl;
//    for (int i = 1; i < next_id; i++)
//        cout << i << " -p-> " << p[i] << endl;

    vector<int> ord;
    ord.push_back(1);
    i = 0;
    while (i < ord.size()) {
        for (int j = 0; j < VOCAB; j++)
            if (f[ord[i]][j])
                ord.push_back(f[ord[i]][j]);
        i++;
    }

    for (int i = ord.size() - 1; i >= 0; i--) {
        cnt[fail[ord[i]]] += cnt[ord[i]];
    }

    for (int i = 0; i < n; i++)
        cout << cnt[ix[i]] << '\n';

    return 0;
}