Cod sursa(job #2393413)

Utilizator PredaBossPreda Andrei PredaBoss Data 31 martie 2019 14:10:42
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct trie
{
    trie *child[26];
    trie *fail;
    int val;
    int ap;
    trie()
    {
        for(int i=0;i<26;i++)child[i]=0;
        fail=0;
        val=0;
        ap=0;
    }
};
trie *root=new trie();
trie *q[1000005];
trie *lst[1000005];
trie *ending[105];
int n,k,l,ans,length;
string sir;
string t;
void add(int it)
{
    trie *where=root;
    k=t.size();
    for(int i=0;i<k;i++)
    {
        if(where->child[t[i]-'a']==0)
        {
            where->child[t[i]-'a']=new trie();
            where->child[t[i]-'a']->val=t[i]-'a';
        }
        where=where->child[t[i]-'a'];
    }
    ending[it]=where;
}
void find_fail()
{
    root->fail=root;
    q[0]=root;
    lst[0]=root;
    length=1;
    int where=0;
    while(where<length)
    {
        trie *pos=q[where];
        trie *last=lst[where];
        where++;
        last=last->fail;
        int v=pos->val;
        while(last!=root && last->child[v]==0)
            last=last->fail;
        if(last==root)
        {
            if(last->child[v]!=0 && pos!=root && pos!=last->child[v])
                pos->fail=last->child[v];
            else
                pos->fail=root;
        }
        else
            pos->fail=last->child[v];
        for(int i=0;i<='z'-'a';i++)
            if(pos->child[i]!=0)
            {
                q[length]=pos->child[i];
                lst[length]=pos;
                length++;
            }
    }
}
void solve()
{
    trie *where;
    for(int i=length-1;i>0;i--)
    {
        where=q[i];
        if(where->fail!=root)
        (where->fail)->ap+=where->ap;
    }
}
int main()
{
    fin>>sir;
    fin>>n;
    for(int it=1;it<=n;it++)
    {
        fin>>t;
        add(it);
    }
    find_fail();
    trie *where=root;
    for(int i=0;i<sir.size();i++)
    {
        while(where!=root && where->child[sir[i]-'a']==0)
            where=where->fail;
        if(where->child[sir[i]-'a']!=0)
            where=where->child[sir[i]-'a'];
        where->ap++;
    }
    solve();
    for(int i=1;i<=n;i++)
        fout<<ending[i]->ap<<"\n";
    return 0;
}