Pagini recente » Cod sursa (job #827245) | Cod sursa (job #2396398) | Monitorul de evaluare | Cod sursa (job #2616183) | Cod sursa (job #2900052)
#include <bits/stdc++.h>
#define car(x) (x-'a')
#define Nmax 1000005
#define Pmax 10005
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;
vector<int> ind;
int cnt;
trie()
{
for(int i=0;i<26;i++)
fii[i]=nullptr;
suffix_link=nullptr;
cnt=0;
}
};
trie *root = new trie();
stack <trie*> invbfs;
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();
invbfs.push(u);
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]);
}
}
}
void ahoaho(trie *root, char c[])
{
int n=strlen(c);
trie *nod = root;
for(int i=0;i<n;i++)
{
while(nod->fii[car(c[i])]==nullptr && nod != root)
nod = nod->suffix_link;
if(nod->fii[car(c[i])]!=nullptr) nod = nod->fii[car(c[i])];
nod->cnt++;
}
}
void antibfs()
{
while(!invbfs.empty())
{
trie *u = invbfs.top();
invbfs.pop();
if(u->suffix_link!=nullptr) u->suffix_link->cnt += u->cnt;
for(auto it:u->ind)
ap[it]+=u->cnt;
}
}
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);
antibfs();
for(int i=1;i<=nr_cuv;i++)
fout << ap[i] << '\n';
return 0;
}