Cod sursa(job #1964862)

Utilizator razvandRazvan Dumitru razvand Data 13 aprilie 2017 19:10:27
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");

const int maxA = 1000003;
const int maxC = 10003;
const int maxN = 103;
const int alf = 26;

int n;
int g[maxC*maxN][alf];
int tim=1;
int f[maxC*maxN];
int viz[maxC*maxN];
vector<int> poz[maxC*maxN];
string st;
string words[maxC];
stack<int> antib;
int ans[maxC];

void ins(string &s, int i, int cstate, int val) {
    while(i != s.size()) {
        if(g[cstate][s[i]-'a'] == 0)
            g[cstate][s[i]-'a'] = ++tim;
        cstate = g[cstate][s[i]-'a'];
        i++;
    }
    poz[cstate].push_back(val);
}

void bfs() {
    queue<int> q;
    for(int i = 0; i < alf; i++) {
        if(g[1][i] != 0) {
            f[g[1][i]] = 1;
            q.push(g[1][i]);
        } else
            g[1][i] = 1;
    }
    f[1] = 1;
    int cstate;
    while(!q.empty()) {
        cstate = q.front();
        antib.push(cstate);
        q.pop();
        for(int i = 0; i < 26; i++) {
            if(g[cstate][i] != 0 && g[cstate][i] != 1) {
                int F = f[cstate];
                while(g[F][i] == 0)
                    F = f[F];
                f[g[cstate][i]] = g[F][i];
                q.push(g[cstate][i]);
            }
        }
    }
}

void dfs(int cstate, int p) {
    while(p != st.size()) {
        viz[cstate]++;
        while(g[cstate][st[p]-'a'] == 0)
            cstate = f[cstate];
        cstate = g[cstate][st[p]-'a'];
        p++;
    }
    viz[cstate]++;
}

void antibfs() {
    int crr;
    while(!antib.empty()) {
        crr = antib.top();
        antib.pop();
        for(int i = 0; i < poz[crr].size(); i++)
            ans[poz[crr][i]] = viz[crr];
        viz[f[crr]] += viz[crr];
    }
}

int main() {

    in >> st;
    in >> n;

    for(int i = 1; i <= n; i++) {
        in >> words[i];
        ins(words[i], 0, 1, i);
    }

    bfs();
    dfs(1, 0);
    antibfs();

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

    return 0;
}