Cod sursa(job #1766122)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 27 septembrie 2016 16:19:20
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100010
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");

string A, B;
int N, App[111];

struct Node {
    int X;
    vector<int> Words;
    struct Node *F[26], *Prev;
    Node() {
        memset(F, 0, sizeof(F));
        Prev = 0;
        X = 0;
        Words.resize(0);
    }
};

struct Trie{
    Node *R;
    vector<Node*> Q;

    Trie() {
        R = new Node();
        Q.resize(0);
    }

    void Add(string B, int K) {
        Node *It = R;
        int U;
        for (int i = 0; i < B.length(); i++) {
            U = B[i]-'a';
            if (It->F[U] == NULL) {
                It->F[U] = new Node();
            }
            It = It->F[U];
        }
        It->Words.push_back(K);
    }

    void BFS() {
        Node *It, *T;
        int U;
        R->Prev = R;
        Q.push_back(R);
        for (int i = 0; i < Q.size(); i++) {
            It = Q[i];
            for (int U = 0; U < 26; U++)
            if (It->F[U]) {
                for (T = It->Prev; T != R && T->F[U] == 0; T = T->Prev);
                if (T->F[U] != 0 && T != It) T = T->F[U];
                It->F[U]->Prev = T;
                Q.push_back(It->F[U]);
            }
        }
        R->Prev = 0;
    }

    void Calculate() {
        Node *It = R;
        int U;
        for (int i = 0; i < A.length(); i++) {
            U = A[i]-'a';
            while (It != R && It->F[U] == 0) It = It->Prev;
            if (It->F[U]) {
                It = It->F[U];
                It->X++;
            }
        }
    }

    void Extract() {
        Node *It;
        for (int i = Q.size() - 1; i >= 0; i--) {
            It = Q[i];
            for (int j = 0; j < It->Words.size(); j++) {
                App[It->Words[j]] = It->X;
            }
            if (It->Prev) It->Prev->X += It->X;
        }
    }

} *T;

int main() {

    T = new Trie();

    f >> A;
    f >> N;
    for (int i = 1; i <= N; i++) {
        f >> B;
        T->Add(B, i);
    }
    T->BFS();
    T->Calculate();
    T->Extract();

    for (int i = 1; i <= N; i++) {
        g << App[i] << "\n";
    }

    return 0;
}