Pagini recente » Cod sursa (job #1280248) | Cod sursa (job #630339) | Cod sursa (job #1194712) | Cod sursa (job #1335607) | Cod sursa (job #2738012)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct trie
{
int n0;
vector <int> indici;
trie *v[27],*fail;
trie ()
{
n0=0;
fail=0;
indici.clear();
for (int j=0;j<=26;j++)
{
v[j]=nullptr;
}
}
}*t,*q[100005];
int qe;
void insereaza(trie *tree,char *t,int indice)
{
if (!*t)
{
tree->indici.push_back(indice);
return;
}
int loc=*t-'a';
if (tree->v[loc]==nullptr)
{
tree->v[loc]=new trie();
}
insereaza(tree->v[loc],t+1,indice);
}
void bfs ()
{
t->fail= t;
q[++qe]=t;
for (int i=1;i<=qe;i++)
{
trie *crt=q[i];
for (int j=0;j<=26;j++)
{
if (crt->v[j]!=nullptr)
{
trie *fiu=crt->fail;
while (fiu!=t&&fiu->v[j]==nullptr)
{
fiu=fiu->fail;
}
if (fiu->v[j]&&fiu->v[j]!=crt->v[j])
{
fiu=fiu->v[j];
}
crt->v[j]->fail=fiu;
q[++qe]=crt->v[j];
}
}
}
t->fail=0;
}
char s[1000005],s1[10005];
int n,i;
int n1;
void kmp()
{
trie *p=t;
n1=strlen(s);
for (int i=0;i<n1;i++)
{
int lit=s[i]-'a';
while (!p->v[lit]&&p!=t)
{
p=p->fail;
}
if (p->v[lit])
{
p=p->v[lit];
}
p->n0++;
}
}
int sol[105];
void antibfs()
{
while (qe)
{
trie *crt=q[qe];
qe--;
if (crt->fail)
{
crt->fail->n0+=crt->n0;
}
for (int j=0;j<crt->indici.size();j++)
{
sol[crt->indici[j]]=crt->n0;
}
}
}
int main()
{
f>>s;
f>>n;
t=new trie();
for (i=1;i<=n;i++)
{
f>>s1;
insereaza(t,s1,i);
}
bfs();
kmp();
antibfs();
for (i=1;i<=n;i++)
{
g<<sol[i]<<'\n';
}
return 0;
}