Cod sursa(job #877637)

Utilizator enedumitruene dumitru enedumitru Data 13 februarie 2013 00:18:04
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <cstring> 
#include <fstream> 
#include <vector> 
#include <queue> 
using namespace std; 
ifstream f("ahocorasick.in"); ofstream g("ahocorasick.out");   
struct trie 
{   int val; 
    trie *son[26], *next; 
    vector <trie *> V; 
    trie() 
    {   memset(son,0,sizeof(son)); 
        val=0;
		next=0; 
    } 
}; 
trie *T=new trie; 
trie *add(trie *now, char *chn) 
{   if(*chn==0) return now; 
    if(now->son[*chn-'a']==0) 
    {   trie *aux=new trie; 
        now->son[*chn-'a']=aux; 
    } 
    now=now->son[*chn-'a']; 
    ++chn; 
    return add(now, chn); 
} 
int N; 
char A[1000002], B[102][10002]; 
queue<trie*> Q; 
trie *where[102]; 
void Dfs(trie *now) 
{   for (vector<trie*>::iterator it = now->V.begin(); it != now->V.end(); ++it) 
    {   Dfs(*it); 
        now->val += (*it)->val; 
    } 
} 
int main() 
{   f>>A>>N; 
    for(int i=1; i<=N; ++i) 
    {   f>>B[i]; 
        where[i]=add(T,B[i]); 
    } 
    Q.push(T); 
    while(!Q.empty()) 
    {   trie *now=Q.front(); Q.pop(); 
        for(int i=0; i<26; ++i) 
            if(now->son[i]!=0) 
            {   trie *aux=now->next; 
                while(aux && aux->son[i]==0) aux=aux->next; 
                if(aux) 
                {   now->son[i]->next=aux->son[i]; 
                    aux->son[i]->V.push_back(now->son[i]); 
                } 
                else
                {   now->son[i]->next=T; 
                    T->V.push_back(now->son[i]); 
                } 
                Q.push(now->son[i]); 
            } 
    } 
    trie *now=T; 
    for(int i=0; A[i]!=0; ++i) 
    {   while(now && now->son[A[i]-'a']==0) now = now->next; 
        if(!now) now = T; 
        else
        {   now=now->son[A[i]-'a']; ++now->val;} 
    } 
    Dfs(T); 
    for (int i=1; i<=N; ++i) g<<where[i]->val<< '\n'; 
    g.close(); 
}