Cod sursa(job #2245167)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 24 septembrie 2018 19:51:49
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.03 kb
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;

#define NMAX 101
#define ALPHA 26

struct Prefix {
    int next[ALPHA];
    int link, p;
    char pch;
    bool leaf;
    int cnt;
    vector <int> idx;

    Prefix(int p = -1, char pch = '$') {
        fill(begin(next), end(next), -1);
        link = -1;
        leaf = false;
        cnt = 0;
        this->p = p;
        this->pch = pch;
    }
};

vector <Prefix> v(1);
int sol[NMAX];

void add_string(const string& s, int idx) {
    int q = 0;
    for (const char& ch : s) {
        int idx = ch - 'a';
        if (v[q].next[idx] == -1) {
            v[q].next[idx] = v.size();
            v.emplace_back(q, ch);
        }
        q = v[q].next[idx];
    }
    v[q].leaf = true;
    v[q].idx.push_back(idx);
}

int get_suffix(const int p) {
    if (v[p].link != -1)
        return v[p].link;
    if (p == 0 || v[p].p == 0) {
        v[p].link = 0;
        return 0;
    }
    int plink = get_suffix(v[p].p);
    while (plink) {
        if (v[plink].next[v[p].pch - 'a'] != -1)
            break;
        plink = get_suffix(plink);
    }
    if (v[plink].next[v[p].pch - 'a'] != -1) {
        v[p].link = v[plink].next[v[p].pch - 'a'];
    } else {
        v[p].link = 0;
    }
    return v[p].link;
}

void build_links() {
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        v[node].link = get_suffix(node);
        for (int i = 0; i < ALPHA; i++) {
            if (v[node].next[i] != -1)
                q.push(v[node].next[i]);
        }
    }
}

int main () {
    int n;
    string a;
    ifstream f("ahocorasick.in");
    ofstream g("ahocorasick.out");
    f >> a;
    f >> n;
    for (int i = 1; i <= n; i++) {
        string b;
        f >> b;
        add_string(b, i);
    }
    f.close();
    build_links();
    int q = 0;
    for (const char& ch : a) {
        int idx = ch - 'a';
        while (q) {
            if (v[q].next[idx] != -1)
                break;
            q = v[q].link;
        }
        if (v[q].next[idx] != -1) {
            q = v[q].next[idx];
        }
        if (q) {
            v[q].cnt++;
        }
    }
    vector <int> ord;
    {
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            ord.push_back(node);
            for (int i = 0; i < ALPHA; i++) {
                if (v[node].next[i] != -1)
                    q.push(v[node].next[i]);
            }
        }
    }
    reverse(ord.begin(), ord.end());
    for (const int node : ord) {
        v[v[node].link].cnt += v[node].cnt;
    }
    for (const int node : ord) {
        if (v[node].leaf) {
            for (const int idx : v[node].idx)
                sol[idx] = v[node].cnt;
        }
    }
    for (int i = 1; i <= n; i++) {
        g << sol[i] << '\n';
    }
    g.close();
    return 0;
}