Cod sursa(job #2531390)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 26 ianuarie 2020 11:20:50
Problema Aho-Corasick Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.98 kb
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

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

const int SIGMA = 26;
const int NMAX = 100;
const int WORDMAX = 10000;
const int TEXTMAX = 1000000;

struct Trie
{
    Trie *sons[SIGMA];
    Trie *failLink;

    vector< int > wordlist;
    int Count;

    Trie()
    {
        failLink = NULL;

        for(int i = 0; i < SIGMA; i++)
            sons[i] = NULL;

        Count = 0;
    }
};

int N;
char Text[TEXTMAX + 5], Word[WORDMAX + 5];

Trie *Root = new Trie();

queue < Trie* > Q;
vector < Trie* > antibfs;

int freq[NMAX + 5];

void Insert(Trie *root, char *word, int wordId)
{
    if(word[0] == '\0')
        root->wordlist.push_back(wordId);
    else
    {
        if(root->sons[word[0] - 'a'] == NULL)
            root->sons[word[0] - 'a'] = new Trie();

        Insert(root->sons[word[0] - 'a'], word + 1, wordId);
    }
}

void computeAhoLinks()
{
    Root->failLink = Root;

    for(int i = 0; i < SIGMA; i++)
        if(Root->sons[i] != NULL)
        {
            Root->sons[i]->failLink = Root;
            Q.push(Root->sons[i]);
        }

    while(!Q.empty())
    {
        Trie *node = Q.front();
        Q.pop();

        for(int i = 0; i < SIGMA; i++)
        {
            if(node->sons[i] != NULL)
            {
                Trie *failNode = node->failLink;

                while(failNode != Root && failNode->sons[i] == NULL)
                    failNode = failNode->failLink;

                if(failNode->sons[i] != NULL && failNode->sons[i] != node->sons[i])
                    failNode = failNode->sons[i];

                node->sons[i]->failLink = failNode;

                Q.push(node->sons[i]);
            }
        }
    }
}

void Solve(Trie *root, char *text)
{
    Trie *node = root;
    while(text[0] != '\0')
    {
        while(node != Root && node->sons[*text - 'a'] == NULL)
            node = node->failLink;

        if(node->sons[text[0] - 'a'] != NULL)
            node = node->sons[text[0] - 'a'];

        node->Count ++;
        text++;
    }


    Q.push(root);
    while(!Q.empty())
    {
        Trie *node = Q.front();
        Q.pop();
        antibfs.push_back(node);

        for(int i = 0; i < SIGMA; i++)
            if(node->sons[i] != NULL)
                Q.push(node->sons[i]);
    }

    reverse(antibfs.begin(), antibfs.end());
    for(auto node : antibfs)
    {
        for(auto wordId : node->wordlist)
            freq[wordId] += node->Count;

        if(node->failLink != NULL)
            node->failLink->Count += node->Count;
    }

    for(int i = 1; i <= N; i++)
        fout << freq[i] << '\n';
}

int main()
{
    fin >> Text;

    fin >> N;

    for(int i = 1; i <= N; i++)
    {
        fin >> Word;
        Insert(Root, Word, i);
    }

    computeAhoLinks();

    Solve(Root, Text);

    return 0;
}