Cod sursa(job #1757483)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 15 septembrie 2016 10:15:58
Problema Aho-Corasick Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <map>

using namespace std;

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

const int dim = 1000005;

struct Node {

    int len, link;
    map< int, int > next;

    Node() {
        len = link = 0;
    }

} nodes[2 * dim];

int sz, last;

void Init() {

    sz = last = 0;
    nodes[0].len = 0;
    nodes[0].link = -1;
    sz++;

}

set< pair<int, int> > base;
int cnt[2 * dim];

void Update(int letter) {

    int curr = sz++;
    nodes[curr].len = nodes[last].len + 1;

    cnt[curr] = 1;
    base.insert(make_pair(nodes[curr].len, curr));

    int p;
    for (p = last; p != -1 && !nodes[p].next.count(letter); p = nodes[p].link)
        nodes[p].next[letter] = curr;

    if (p == -1)
        nodes[curr].link = 0;
    else {

        int q = nodes[p].next[letter];
        if (nodes[p].len + 1 == nodes[q].len)
            nodes[curr].link = q;
        else {

            int clone = sz++;
            nodes[clone].len = nodes[p].len + 1;
            nodes[clone].next = nodes[q].next;
            nodes[clone].link = nodes[q].link;

            cnt[clone] = 0;
            base.insert(make_pair(nodes[clone].len, clone));

            for (; p != -1 && nodes[p].next[letter] == q; p = nodes[p].link)
                nodes[p].next[letter] = clone;

            nodes[q].link = nodes[curr].link = clone;

        }

    }

    last = curr;

}

void BuildCnt() {

    for (set< pair<int, int> >::reverse_iterator it = base.rbegin(); it != base.rend(); ++it)
        cnt[nodes[it->second].link] += cnt[it->second];

}

int CountOccurances(const string pattern) {

    size_t pos = 0;
    int curr = 0;

    while (pos < pattern.length() && nodes[curr].next.count(pattern[pos] - 'a'))
        curr = nodes[curr].next[pattern[pos] - 'a'], pos++;

    return (curr == -1 ? 0 : cnt[curr]);

}

int main() {

    string a;
    fin >> a;

    Init();
    for (size_t i = 0; i < a.length(); ++i)
        Update(a[i] - 'a');
    BuildCnt();

    int n; fin >> n;
    while (n--) {

        fin >> a;
        fout << CountOccurances(a) << '\n';

    }

    return 0;

}

//Trust me, I'm the Doctor!