Cod sursa(job #2193464)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 10 aprilie 2018 11:38:56
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>
using namespace std;

vector <int> lvls[100010];
vector <vector <int>> v;
vector <int> fail, letter, frc;
int words[100010];

int nou(int q)
{
    int x = v.size();
    v.push_back(vector <int> (27));
    fail.push_back(0);
    letter.push_back(q);
    frc.push_back(0);
    return x;
}

void add(string s, int word)
{
    int root = 0;
    int lvl(0);
    for (auto & i : s) {
        i -= 'a';
        lvl++;
        if (!v[root][i]) {
            int x = nou(i);
            v[root][i] = x;
            lvls[lvl].push_back(x);
        }
        root = v[root][i];
    }
    words[word] = root;
}

void calc_fail()
{
    for (int x(0); x <= 100000; x++) {
        for (auto i : lvls[x]) {
            while (fail[i] &&
              (!v[fail[i]][letter[i]] || v[fail[i]][letter[i]] == i))
                fail[i] = fail[fail[i]];
            if (v[fail[i]][letter[i]] &&
              v[fail[i]][letter[i]] != i)
                fail[i] = v[fail[i]][letter[i]];
            for (int j(0); j < 26; j++)
                if (v[i][j])
                    fail[v[i][j]] = fail[i];
        }
    }
}

void calc_ans()
{
    for (int x(100000); x >= 0; x--)
        for (auto i : lvls[x])
            frc[fail[i]] += frc[i];
}

int main()
{
    ifstream in("ahocorasick.in");
    ofstream out("ahocorasick.out");
    string s;
    in >> s;

    nou(-1);

    int n;
    in >> n;

    for (int i(1); i <= n; i++) {
        string q;
        in >> q;
        add(q, i);
    }

    calc_fail();

    int root = 0;

    for (auto i : s) {
        while (root && !v[root][i - 'a'])
            root = fail[root];
        if (v[root][i - 'a'])
            root = v[root][i - 'a'];
        frc[root]++;
    }
    calc_ans();

    for (int i(1); i <= n; i++)
        out << frc[words[i]] << '\n';

    return 0;
}