Cod sursa(job #1415801)

Utilizator danalex97Dan H Alexandru danalex97 Data 6 aprilie 2015 12:59:28
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.89 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

ifstream F("ahocorasick.in");
ofstream G("ahocorasick.out");

const int N = 1000010;
const int M = 10010;
const int K = 110;

struct aho {
    int cnt;
    vector<int> words;

    aho *sons[26],*fail;

    aho()
    {
        cnt = 0;
        fail = NULL;
        memset(sons,0,sizeof(sons));
    }
} *tree, *p;

int ans[K];
vector<aho*> stk;

void insert(aho *tree,char *str,int index)
{
    if ( *str >= 'a' && *str <= 'z' )
    {
        int where = int(*str) - int('a');
        if ( tree->sons[where] == NULL )
        {
            tree->sons[where] = new aho;
        }
        insert(tree->sons[where],str+1,index);
    }
    else
    {
        tree->words.push_back( index );
        return;
    }
}

void bfs(aho *tree) /// add fails
// the previous nodes are already built , so run something similar to KMP
{
    queue< aho* > q;
    tree->fail = tree;
    q.push(tree);

    while ( !q.empty() )
    {
        aho *now = q.front();
        q.pop();

        for (int i=0;i<26;++i)
            if ( now->sons[i] != NULL )
            {
                aho* aux = now->fail;
                while ( aux != tree && aux->sons[i] == NULL )
                // if I haven't reached the root and the requested son doesn't exist
                // go backwards ( like in pi function at KMP )
                    aux = aux->fail;

                if ( aux->sons[i] != NULL && aux->sons[i] != now->sons[i] )
                // normally go to the son , but there are cases where the fail remains a
                // backward edge
                    aux = aux->sons[i];
                now->sons[i]->fail = aux;

                q.push( now->sons[i] );
                stk.push_back( now->sons[i] );
            }
    }
    tree->fail = NULL;
}

void reverse_bfs() // computes the solution
// add the cnt from the node to the bigest common suffix
{
    for (;!stk.empty();stk.pop_back())
    {
        aho *now = stk.back();
        if ( now->fail != NULL )
            now->fail->cnt += now->cnt;
        for (int j=0;j<int(now->words.size());++j)
            ans[ now->words[j] ] = now->cnt;
    }
}

char text[N],word[N];
int n;

int main()
{
    F>>text;
    F>>n;

    tree = new aho;
    for (int i=1;i<=n;++i)
    {
        F>>word;
        insert(tree,word,i);
    }

    bfs(tree);

    p = tree; // p is the pointer that travels inside the automaton

    int ln = strlen(text);
    for (int i=0;i<ln;++i)
    {
        int where = int(text[i]) - int('a');
        while ( p->sons[where] == NULL && p != tree )
            p = p->fail;
        if ( p->sons[where] != NULL )
            p = p->sons[where];
        ++p->cnt;
    }

    reverse_bfs();

    for (int i=1;i<=n;++i)
        G<<ans[i]<<'\n';
}