Pagini recente » Cod sursa (job #1289693) | Istoria paginii runda/prbd2 | Cod sursa (job #1635366) | Cod sursa (job #1645446) | Cod sursa (job #2899804)
#include <bits/stdc++.h>
#define car(x) (x-'a')
#define Nmax 1000005
#define Pmax 1005
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int n, nr_cuv, ap[Pmax];
char c[Nmax], p[Pmax];
struct trie
{
trie *fii[26], *suffix_link, *output_link;
vector<int> ind;
trie()
{
for(int i=0;i<26;i++)
fii[i]=nullptr;
suffix_link=nullptr;
output_link=nullptr;
}
};
trie *root = new trie();
void ins(trie *root, char p[], int index)
{
int n=strlen(p);
trie *nod = root;
for(int i=0;i<n;i++)
{
if(nod->fii[car(p[i])]==nullptr)
nod->fii[car(p[i])] = new trie();
nod = nod->fii[car(p[i])];
}
nod->ind.push_back(index);
}
void bfs(trie *root)
{
queue <trie*> q;
for(int i=0;i<26;i++)
if(root->fii[i]!=nullptr)
{
q.push(root->fii[i]);
root->fii[i]->suffix_link=root;
}
while(!q.empty())
{
trie *u = q.front();
q.pop();
for(int i=0;i<26;i++)
if(u->fii[i]!=nullptr)
{
trie *suffix = u->suffix_link;
while(suffix->fii[i]==nullptr && suffix!=root)
suffix = suffix->suffix_link;
if(suffix->fii[i]!=nullptr)
u->fii[i]->suffix_link = suffix->fii[i];
else u->fii[i]->suffix_link = root;
q.push(u->fii[i]);
}
if(u->suffix_link->ind.size() > 0)
u->output_link = u->suffix_link;
else u->output_link = u->suffix_link->output_link;
}
}
void ahoaho(trie *root, char c[])
{
int n=strlen(c);
trie *nod = root;
for(int i=0;i<n;i++)
if(nod->fii[car(c[i])]!=nullptr)
{
nod = nod->fii[car(c[i])];
if(nod->ind.size()>0)
for(auto it:nod->ind)
ap[it]++;
trie *aux = nod->output_link;
while(aux!=nullptr)
{
for(auto it:aux->ind)
ap[it]++;
aux=aux->output_link;
}
}
else
{
while(nod != root && nod->fii[car(c[i])]==nullptr)
nod=nod->suffix_link;
if(nod->fii[car(c[i])])
i--;
}
}
int main()
{
fin >> c;
fin >> nr_cuv;
for(int i=1;i<=nr_cuv;i++)
{
fin >> p;
ins(root, p, i);
}
bfs(root);
ahoaho(root, c);
for(int i=1;i<=nr_cuv;i++)
fout << ap[i] << '\n';
return 0;
}