Cod sursa(job #1761870)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 23 septembrie 2016 00:06:07
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
///Try II
#include <bits/stdc++.h>
using namespace std;

const int SIGM = 26;

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

struct Aho {
    Aho *tr[SIGM], *fail;
    vector<int> ordbok;
    int match;

    inline Aho() {
        memset(tr, 0x00, sizeof(tr));
        match = 0;
        fail = NULL;
    }
};

int n, pindex;
Aho *rt;

int ant[105];
vector<Aho*> rvq;

void put(const string &pat) {
    Aho *now = rt;
    for(const char &ch: pat) {
        if(!now->tr[ch-'a'])
            now->tr[ch-'a'] = new Aho();
        now = now->tr[ch-'a'];
    }
    now->ordbok.push_back(++pindex);
}

void bfs(void) {
    queue<Aho*> q;
    Aho *now, *tmp;

    rt->fail = rt;
    q.push(rt);

    while(!q.empty()) {
        now = q.front();
        q.pop();

        for(int i=0; i<SIGM; ++i) if(now->tr[i]) {
            q.push(now->tr[i]);
            rvq.push_back(now->tr[i]);

            for(tmp=now->fail; tmp!=rt && !tmp->tr[i]; tmp=tmp->fail);

            if(tmp->tr[i]!=NULL && tmp->tr[i]!=now->tr[i])
                tmp = tmp->tr[i];

            now->tr[i]->fail = tmp;
        }
    }
}

void sturmgewahr(const string &txt) {
    Aho *now = rt;

    for(const char &ch: txt) {
        while(now!=rt && !now->tr[ch-'a'])
            now = now->fail;
        if(now->tr[ch-'a'])
            now = now->tr[ch-'a'];
        ++ now->match;
    }
}

void anti_bfs(void) {
    for(int i=rvq.size()-1; i>=0; --i) {
        if(rvq[i]->fail)
            rvq[i]->fail->match += rvq[i]->match;

        for(const auto &j: rvq[i]->ordbok)
            ant[j] = rvq[i]->match;
    }
}

int main(void) {
    string txt, pat;

    rt = new Aho();

    fi >> txt >> n;
    for(int i=1; i<=n; ++i) {
        fi >> pat;
        put(pat);
    }

    bfs();
    sturmgewahr(txt);
    anti_bfs();

    for(int i=1; i<=n; ++i)
        fo << ant[i] << '\n';

    return 0;
}