Cod sursa(job #1862118)

Utilizator Bodo171Bogdan Pop Bodo171 Data 29 ianuarie 2017 15:51:24
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int www;
struct Trie
{
    vector<int> strings;
    int ap;
    Trie *son[26],*fail;
    Trie()
    {
        fail=0;ap=0;
        for(www=0;www<26;www++)
           son[www]=0;
    }
}*rad=new Trie,*q[100005],*node,*pi;
string a,s;
int n,ind,i,j,p,u,wh;
int ans[105];
void ins(Trie *node)
{
    for(ind=0;ind<a.size();ind++)
    {
        wh=a[ind]-'a';
        if(node->son[wh]==0)
            node->son[wh]=new Trie;
        node=node->son[wh];
    }
    node->strings.push_back(i);
}
void calc_suffix()
{
    q[1]=rad;p=1;u=1;
    rad->fail=rad;
    while(p<=u)
    {
        node=q[p];p++;
        for(i=0;i<26;i++)
            if(node->son[i]!=0)
        {
            pi=node->fail;
            while(pi!=rad&&pi->son[i]==0)
            {
                pi=pi->fail;
            }
            if(pi->son[i]!=0&&pi!=node)pi=pi->son[i];
            node->son[i]->fail=pi;
            u++;q[u]=node->son[i];
        }
    }
}
void match()
{
    node=rad;
    for(i=0;i<s.size();i++)
    {
        wh=s[i]-'a';
        while(node!=rad&&node->son[wh]==0)
            node=node->fail;
        if(node->son[wh]!=0)
            node=node->son[wh];
        node->ap++;
    }
}
void propag()
{
    for(i=u;i>=1;i--)
    {
        node=q[i];
        node->fail->ap+=node->ap;
        for(j=0;j<node->strings.size();j++)
            ans[node->strings[j]]=node->ap;
    }
}
int main()
{
    ifstream f("ahocorasick.in");
    ofstream g("ahocorasick.out");
    f>>s;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a;
        ins(rad);
    }
    calc_suffix();
    match();
    propag();
    for(i=1;i<=n;i++)
        g<<ans[i]<<'\n';
    return 0;
}