Cod sursa(job #868700)

Utilizator stoicatheoFlirk Navok stoicatheo Data 31 ianuarie 2013 15:00:45
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <cstdio>
#include <cstring>
 
using namespace std;
 
#define maxl 1000010
#define maxs 10010
#define maxt 100010
#define sigma 27
#define maxn 110
 
int n, nn, m, lg, lp;
int q[maxt], sol[maxn], where[maxn];
struct trie
{
    int nap, up, f[sigma];
} t[maxt];
char p[maxl], sc[maxs];
 
int add()
{
    lg=strlen(sc);
    int nc=1;
    for(int i=0; i<lg; ++i)
    {
        sc[i]-='a';
        if(t[nc].f[sc[i]]==0)
            t[nc].f[sc[i]]=++nn;
        nc=t[nc].f[sc[i]];
        sc[i]=0;
    }
    return nc;
}
 
void bfs(int nc)
{
    int q0=1, fiu, aux;
 
    q[q0]=nc;
    t[1].up=1;
    for(int i=1; i<=q0; ++i)
    {
        nc=q[i];
        for(int j=0; j<sigma; ++j)
        {
            if(t[nc].f[j]==0)
                continue;
 
            aux=t[nc].up;
            while(aux!=1 && t[aux].f[j]==0)
                aux=t[aux].up;
            if(t[aux].f[j]!=0 && t[aux].f[j]!=t[nc].f[j])
                aux=t[aux].f[j];
 
            q[++q0]=t[nc].f[j];
            t[t[nc].f[j]].up=aux;
        }
    }
}
 
void solve()
{
    int nc=1;
    char cc;
    for(int i=0; i<lp; ++i)
    {
        cc=p[i]-'a';
        while(t[nc].f[cc]==0 && nc>1)
            nc=t[nc].up;
        if(t[nc].f[cc]!=0)
            nc=t[nc].f[cc];
        ++t[nc].nap;
    }
 
    for(int i=nn; i>1; --i)
    {
        nc=q[i];
        t[t[nc].up].nap+=t[nc].nap;
    }
 
    for(int i=1; i<=n; ++i)
        sol[i]=t[where[i]].nap;
}
 
int main()
{
    freopen("ahocorasick.in", "r", stdin);
    freopen("ahocorasick.out", "w", stdout);
 
    scanf("%s", p);
    lp=strlen(p);
    nn=1;
 
    scanf("%d\n", &n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%s", sc);
        where[i]=add();lg=strlen(sc);
    }
 
    bfs(1);
    solve();
 
    for(int i=1; i<=n; ++i)
        printf("%d\n", sol[i]);
 
    return 0;
}