Cod sursa(job #2188286)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 27 martie 2018 02:41:40
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;

struct trie{
    trie *f[26], *fail;
    vector<int> v;
    int occ;
    trie(){
        occ = 0;
        fail = NULL;
        memset(f, 0, sizeof(f));
    }
};

const string fisier = "ahocorasick";
char r[1000005], c[10005];
int n, sol[105], szr, szc;
trie *rad = new trie;

int main()
{
    ifstream fin (fisier+".in");
    ofstream fout (fisier+".out");
    fin >> r >> n;
    szr = strlen(r);
    for (int i = 1; i <= n; ++i){
        fin >> c;
        szc = strlen(c);
        trie *t = rad;
        for (unsigned j = 0; j < szc; ++j){
            int q = c[j]-'a';
            if(t->f[q] == NULL)
                t->f[q] = new trie;
            t = t->f[q];
        }
        t->v.push_back(i);
    }
    int vf = -1;
    vector<trie*> qu;
    qu.push_back(rad);
    rad->fail = rad;
    while(vf != qu.size()-1){
        trie *t = qu[++vf];
        for (int i = 0; i < 26; ++i)
            if(t->f[i]){
                trie *fail = t->fail;
                while(fail != rad && fail->f[i] == NULL)
                    fail = fail->fail;
                if(fail->f[i] != NULL && fail->f[i] != t->f[i])
                    fail = fail->f[i];
                t->f[i]->fail = fail;
                qu.push_back(t->f[i]);
            }
    }
    rad->fail = NULL;
    trie *t = rad;
    for (unsigned i = 0; i < szr; ++i){
        int q = r[i]-'a';
        while(t != rad && t->f[q] == NULL)
            t = t->fail;
        if(t->f[q] != NULL)
            t = t->f[q];
        ++t->occ;
    }
    for (int i = vf; i >= 0; --i){
        t = qu[i];
        if(t->fail != NULL)
            t->fail->occ += t->occ;
        for (vector<int>::iterator it = t->v.begin(); it != t->v.end(); ++it)
            sol[*it] = t->occ;
    }
    for (int i = 1; i <= n; ++i)
        fout << sol[i] << "\n";
    return 0;
}