Cod sursa(job #2364751)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 4 martie 2019 10:43:58
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <bits/stdc++.h>

#define Nmax 105
#define Amax 1000005
#define Lmax 10005

using namespace std;

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

struct ACnode
{
    vector <int> ends;
    ACnode *fail;
    ACnode *nxt[26];
    ACnode()
    {
        for(int i = 0; i < 26; i++)
            nxt[i] = NULL;
        fail = NULL;
    }
};

ACnode *root;
int N;
int ans[Nmax];
char C[Amax], w[Lmax];

void insert(char *w, int idx)
{
    int N = strlen(w + 1);
    ACnode *currNode = root;
    for(int i = 1; i <= N; i++)
    {
        if(currNode -> nxt[w[i] - 'a'] == NULL)
            currNode -> nxt[w[i] - 'a'] = new ACnode;
        currNode = currNode -> nxt[w[i] - 'a'];
    }
    currNode -> ends.push_back(idx);
}

void DoFail(ACnode *root)
{
    queue < ACnode* > Q;
    root -> fail = root;
    for(int i = 0; i < 26; i++)
        if(root -> nxt[i] != NULL)
        {
            root -> nxt[i] -> fail = root;
            Q.push(root -> nxt[i]);
        }
    while(!Q.empty())
    {
        ACnode *node = Q.front();
        Q.pop();
        for(int i = 0; i < 26; i++)
            if(node -> nxt[i] != NULL)
            {
                ACnode *F = node -> fail;
                while(F != root && F -> nxt[i] == NULL)
                    F = F -> fail;
                if(F -> nxt[i] != NULL)
                    F = F -> nxt[i];
                node -> nxt[i] -> fail = F;
                for(auto it : F -> ends)
                    node -> nxt[i] -> ends.push_back(it);
                Q.push(node -> nxt[i]);
            }
    }
}

int main()
{
    fin >> (C + 1);
    fin >> N;
    root = new ACnode;
    for(int i = 1; i <= N; i++)
    {
        fin >> (w + 1);
        insert(w, i);
    }
    DoFail(root);
    int L = strlen(C + 1);
    ACnode *curr = root;
    for(int i = 1; i <= L; i++)
    {
        while(curr != root && curr -> nxt[C[i] - 'a'] == NULL)
            curr = curr -> fail;
        if(curr -> nxt[C[i] - 'a'] != NULL)
            curr = curr -> nxt[C[i] - 'a'];
        for(auto it : curr -> ends)
            ans[it]++;
    }
    for(int i = 1; i <= N; i++)
        fout << ans[i] << "\n";
    return 0;
}