Cod sursa(job #2231777)

Utilizator HumikoPostu Alexandru Humiko Data 15 august 2018 22:46:20
Problema Aho-Corasick Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.84 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");

class TRIE
{
    public:
        TRIE *suffix_Link;
        TRIE *letter[26];
        int apparitions;

        TRIE()
        {
            for ( int i = 0; i <= 26; ++i )
                letter[i] = nullptr;

            suffix_Link = nullptr;
            apparitions = 0;
        }
};

int n;

TRIE *root;
TRIE *answer[105];

string s;

void insertWord( string word, int indx )
{
    TRIE *current_Root = root;

    for ( auto x : word )
    {
        int current_Position = x-'a';

        if ( current_Root->letter[current_Position] == nullptr )
            current_Root->letter[current_Position] = new TRIE();

        current_Root = current_Root->letter[current_Position];
    }

    answer[indx] = current_Root;
}

queue <TRIE*> road;
stack <TRIE*> reversed_Road;

void buildSuffixLinks()
{
    root->suffix_Link = root;
    road.push(root);

    while ( road.size() )
    {
        TRIE *current_Node = road.front();
        reversed_Road.push(current_Node);
        road.pop();

        for ( int i = 0; i < 26; ++i )
        {
            if ( current_Node->letter[i] )
            {
                TRIE *current_Suffix = current_Node->suffix_Link;

                while ( current_Suffix->letter[i] == nullptr && current_Suffix != root )
                    current_Suffix = current_Suffix->suffix_Link;

                if ( current_Suffix->letter[i] != current_Node->letter[i] )
                    current_Node->letter[i]->suffix_Link = current_Suffix->letter[i];
                else
                    current_Node->letter[i]->suffix_Link = root;

                road.push(current_Node->letter[i]);
            }
        }
    }
}

void getApparitions()
{
    TRIE *current_Root = root;

    for ( auto x:s )
    {
        int current_Position = x-'a';

        while ( current_Root != root && current_Root->letter[current_Position] == nullptr )
            current_Root = current_Root->suffix_Link;

        if ( current_Root->letter[current_Position] )
            current_Root = current_Root->letter[current_Position];

        current_Root->apparitions++;
    }

    while ( reversed_Road.size() )
    {
        TRIE *current_Node = reversed_Road.top();
        reversed_Road.pop();
        current_Node->suffix_Link->apparitions += current_Node->apparitions;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);

    root = new TRIE();

    fin>>s;
    fin>>n;

    for ( int i = 1; i <= n; ++i )
    {
        string word;
        fin>>word;
        insertWord(word, i);
    }

    buildSuffixLinks();
    getApparitions();

    for ( int i = 1; i <= n; ++i )
        fout<<answer[i]->apparitions<<'\n';
}