Cod sursa(job #1553855)

Utilizator ZenusTudor Costin Razvan Zenus Data 20 decembrie 2015 17:08:25
Problema Aho-Corasick Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 260000 + 10;

struct trie
{
    trie *nxt[26];
    trie *phi;
    int nr;

    trie()
    {
        for (int i = 0 ; i < 26 ; ++i)
        nxt[i] = 0;
        phi = 0;
        nr = 0;
    }
};

trie *w[nmax] , *iq[nmax];
trie *root , *q , *x;
string s , t;
int n , p , u , i , c;

void add(trie *node , int p)
{
    if (p == t.size())
    {
        w[i] = node;
        return ;
    }

    int c = t[p] - 'a';

    if (node -> nxt[c]) ;
    else node -> nxt[c] = new trie();

    add(node -> nxt[c] , p + 1);
}

int main()
{
freopen("ahocorasick.in" , "r" , stdin);
freopen("ahocorasick.out" , "w" , stdout);

cin >> s;
cin >> n;
root = new trie();

for (i = 1 ; i <= n ; ++i)
{
    cin >> t;
    add(root , 0);
}

p = 1 , u = 0;
for (i = 0 ; i < 26 ; ++i)
if (root -> nxt[i])
{
    iq[++u] = root -> nxt[i];
    root -> nxt[i] -> phi = root;
}

while (p <= u)
{
    q = iq[p++];

    for (c = 0 ; c < 26 ; ++c)
    if (q -> nxt[c])
    {
        x = q -> phi;

        while (x - root && !x -> nxt[c])
        x = x -> phi;

        if (x -> nxt[c]) x = x -> nxt[c];

        q -> nxt[c] -> phi = x;
        iq[++u] = q -> nxt[c];
    }
}

q = root;
for (i = 0 ; i < s.size() ; ++i)
{
    c = s[i] - 'a';

    while (q - root && !q -> nxt[c])
    q = q -> phi;

    if (q -> nxt[c]) q = q -> nxt[c];

    q -> nr += 1;
}

for (i = u ; i ; --i)
iq[i] -> phi -> nr += iq[i] -> nr;

for (i = 1 ; i <= n ; ++i)
cout << w[i] -> nr << '\n';

return 0;
}