Cod sursa(job #3303752)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 17 iulie 2025 17:15:58
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <bits/stdc++.h>

using namespace std;

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

const int lg=26;

struct trie
{
    trie *children[lg];
    trie *fall;
    int cnt;
    trie()
    {
        cnt=0;
        fall=NULL;
        for (int i=0; i<lg; i++)
            children[i]=NULL;
    }
};

trie *root, *out[105];

queue <trie*> q;

void insert_word (trie *root, string word, int ind)
{
    trie *curr=root;
    for (auto c:word)
    {
        int key=c-'a';
        if (curr->children[key]==NULL)
            curr->children[key]=new trie();
        curr=curr->children[key];
    }
    out[ind]=curr;
}

string s;

void corasick ()
{
    vector <trie*> ord;
    root->fall=root;
    q.push(root);
    while (!q.empty())
    {
        trie *node=q.front();
        q.pop();
        ord.push_back(node);
        for (int i=0; i<lg; i++)
        {
            if (node->children[i]==NULL)
                continue;
            trie *suf=node->fall;
            while (suf!=root && suf->children[i]==NULL)
                suf=suf->fall;
            if (suf->children[i]!=NULL && suf->children[i]!=node->children[i])
                node->children[i]->fall=suf->children[i];
            else
                node->children[i]->fall=root;
            q.push(node->children[i]);
        }
    }
    trie *node=root;
    for (int i=0; i<s.size(); i++)
    {
        int key=s[i]-'a';
        while (node!=root && node->children[key]==NULL)
            node=node->fall;
        if (node->children[key]!=NULL)
            node=node->children[key];
        node->cnt++;
    }
    for (int i=ord.size()-1; i>=0; i--)
        ord[i]->fall->cnt+=ord[i]->cnt;
}

int main()
{
    root=new trie();
    fin >> s;
    int n;
    fin >> n;
    for (int i=1; i<=n; i++)
    {
        string t;
        fin >> t;
        insert_word(root,t,i);
    }
    corasick();
    for (int i=1; i<=n; i++)
        fout << out[i]->cnt << '\n';
    return 0;
}