Pagini recente » Profil Ionel2345 | Istoria paginii utilizator/spx | Monitorul de evaluare | Diferente pentru utilizator/darth_niculus intre reviziile 13 si 12 | Cod sursa (job #2408045)
#include<bits/stdc++.h>
using namespace std;
const int sigma=26;
const int maxN=(1e2)+5;
inline int f(int i)
{
return i-'a'+1;
}
struct trie
{
int sol;
trie *sons[sigma+5];
trie *fail;
vector<trie*> v; //numarul de noduri din trie care au fail-ul in nodul curent
trie()
{
sol=0;
for(int i=0;i<=sigma;i++)
sons[i]=NULL;
fail=NULL;
v.clear();
}
}*root=new trie();
trie *w[maxN];
inline trie* Insert(trie *node,char *s)
{
if(*s==NULL)
{
return node;
}
else
{
if(!node->sons[f(s[0])]) node->sons[f(s[0])]=new trie();
return Insert(node->sons[f(s[0])],s+1);
}
}
inline void dfs(trie *node)
{
for(auto it:node->v)
{
dfs(it);
node->sol+=it->sol;
}
}
char str[maxN],s[maxN];
int n,m;
deque<trie*> q;
trie* aux;
int main()
{
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
scanf("%s",str);
m=strlen(str);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s);
w[i]=Insert(root,s);
}
q.push_back(root);
while(!q.empty())
{
trie *node=q.front();
q.pop_front();
for(int i=1;i<=26;i++)
{
if(node->sons[i])
{
aux=node->fail;
while(aux && aux->sons[i]==NULL) aux=aux->fail;
if(aux==NULL) node->sons[i]->fail=root;
else node->sons[i]->fail=aux->sons[i];
node->sons[i]->fail->v.push_back(node->sons[i]);
q.push_back(node->sons[i]);
}
}
}
aux=root;
for(int i=0;i<m;i++)
{
while(aux!=root && aux->sons[f(str[i])]==NULL) aux=aux->fail;
if(aux->sons[f(str[i])]!=NULL) aux=aux->sons[f(str[i])];
aux->sol++;
}
dfs(root);
for(int i=1;i<=n;i++)
printf("%d\n",w[i]->sol);
return 0;
}