Pagini recente » Cod sursa (job #1621546) | Cod sursa (job #2771851) | Cod sursa (job #1686961) | Cod sursa (job #83390) | Cod sursa (job #2900532)
#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
{
int suffix_link, cnt, fii[26];
vector <int> ind;
trie()
{
suffix_link=-1;
cnt=0;
for(int i=0;i<26;i++)
fii[i]=-1;
}
};
vector <trie> t;
queue <int> q;
stack <int> inv;
void ins(char p[], int index)
{
int n=strlen(p);
int nod = 0;
for(int i=0;i<n;i++)
{
if(t[nod].fii[car(p[i])]==-1)
{
trie aux;
t[nod].fii[car(p[i])]=t.size();
t.push_back(aux);
}
nod=t[nod].fii[car(p[i])];
}
t[nod].ind.push_back(index);
}
void bfs()
{
queue <int> q;
for(int i=0;i<26;i++)
if(t[0].fii[i]!=-1)
{
q.push(t[0].fii[i]);
t[t[0].fii[i]].suffix_link=0;
}
while(!q.empty())
{
int u=q.front();
q.pop();
inv.push(u);
for(int i=0;i<26;i++)
if(t[u].fii[i]!=-1)
{
int suffix = t[u].suffix_link;
while(t[suffix].fii[i]==-1 && suffix!=0)
suffix = t[suffix].suffix_link;
if(t[suffix].fii[i]!=-1)
t[t[u].fii[i]].suffix_link = t[suffix].fii[i];
else t[t[u].fii[i]].suffix_link = 0;
q.push(t[u].fii[i]);
}
}
}
void ahoaho(char c[])
{
int n = strlen(c);
int nod = 0;
for(int i=0;i<n;i++)
{
while(t[nod].fii[car(c[i])]==-1 && nod!=0)
nod = t[nod].suffix_link;
if(t[nod].fii[car(c[i])]!=-1) nod = t[nod].fii[car(c[i])];
t[nod].cnt++;
}
}
void antibfs()
{
while(!inv.empty())
{
int u=inv.top();
inv.pop();
if(t[u].suffix_link!=-1) t[t[u].suffix_link].cnt += t[u].cnt;
for(auto it:t[u].ind)
ap[it]+=t[u].cnt;
}
}
int main()
{
trie root;
t.push_back(root);
fin >> c;
fin >> nr_cuv;
for(int i=1;i<=nr_cuv;i++)
{
fin >> p;
ins(p, i);
}
bfs();
ahoaho(c);
antibfs();
for(int i=1;i<=nr_cuv;i++)
fout << ap[i] << '\n';
return 0;
}