Cod sursa(job #1508988)

Utilizator retrogradLucian Bicsi retrograd Data 23 octombrie 2015 13:03:34
Problema Aho-Corasick Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb
#include <fstream>
#include <iostream>
#include <cassert>
#include <vector>

using namespace std;

struct Nod {
    int bad, parent, cnt, leg[27];
};
Nod T[1000005];
int nodes = 1, root = 1;

int Where[105];

vector<int> G[1000005];
int Count[1000005];

void dfs(int node) {
    for(auto vec : G[node]) {
        dfs(vec);
        Count[node] += Count[vec];
    }
}

void addWord(char str[], int ind) {
    int node = root;

    for(int i=0; str[i]; i++) {
        int &nw = T[node].leg[str[i]-'a'];
        if(nw == 0) nw = ++nodes;
        node = nw;
    }

    Where[ind] = node;
}

void make_links(int node, char pc, int parent) {
    if(node != root) {
        int bad = T[parent].bad;
        while(bad && !T[bad].leg[pc])
            bad = T[bad].bad;

        T[node].bad = (bad) ? T[bad].leg[pc] : root;
        G[T[node].bad].push_back(node);
    }

    for(char c='a'-'a'; c<='z'-'a'; c++)
        if(T[node].leg[c])
            make_links(T[node].leg[c], c, node);
}

void go(char Text[]) {
    int node = root;

    for(int i=0; Text[i]; i++) {
        while(node && !T[node].leg[Text[i]-'a'])
            node = T[node].bad;

        if(node) {
            node = T[node].leg[Text[i]-'a'];
            Count[node] ++;
        } else {
            node = root;
        }
    }
}

char str[50000], se = 0;
void dump(int node) {
    cerr<<node<<"("<<str<<"): ";
    cerr<<"bad: "<<T[node].bad;
    cout<<'\n';

    for(char c='a'; c<='z'; c++) {
        if(T[node].leg[c-'a']) {
            str[se++] = c;
            dump(T[node].leg[c-'a']);
            str[--se] = 0;
        }
    }
}

char Text[1000005], Pattern[50005];


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

    int n;

    fin>>Text>>n;
    for(int i=1; i<=n; i++) {
        fin>>Pattern;
        addWord(Pattern, i);
    }

    make_links(root, 0, 0);

    go(Text); dfs(root);

    //dump(root);

    for(int i=1; i<=n; i++) {
        fout<<Count[Where[i]]<<'\n';
    }

    return 0;
}