Pagini recente » Cod sursa (job #2036997) | Cod sursa (job #1436966) | Cod sursa (job #1392799) | Cod sursa (job #1519506) | Cod sursa (job #2734972)
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
string a;
int n;
bool use[1000005];
struct nod
{
int muchii[29];
char c;
vector<int> leaf;
int go[29];
int suflink=-1,dict=-1;
int parent;
};
nod emptynode;
vector<nod> t;
int sol[1005];
int go(int nod,char c);
int suflink(int nod);
int dict(int nod);
void add(string s,int index)
{
int v=0;
for(int i=0;i<s.size();i++)
{
char c=s[i];
int lit=c-'a'+1;
if(t[v].muchii[lit]==-1)
{
t[v].muchii[lit]=t.size();
nod x=emptynode;
x.c=c;
x.parent=v;
t.push_back(x);
}
v=t[v].muchii[lit];
if(i+1==s.size())
t[v].leaf.push_back(index);
}
}
int suflink(int nod)
{
if(t[nod].suflink!=-1)
return t[nod].suflink;
if(nod==0)
{
t[nod].suflink=0;
return t[nod].suflink;
}
int p=t[nod].parent;
if(p==0)
{
t[nod].suflink=0;
return t[nod].suflink;
}
t[nod].suflink=go(suflink(p),t[nod].c);
return t[nod].suflink;
}
int go(int nod,char c)
{
int lit=c-'a'+1;
if(t[nod].go[lit]!=-1)
return t[nod].go[lit];
if(t[nod].muchii[lit]!=-1)
{
t[nod].go[lit]=t[nod].muchii[lit];
return t[nod].go[lit];
}
if(nod==0)
{
t[nod].go[lit]=0;
return t[nod].go[lit];
}
t[nod].go[lit]=go(suflink(nod),c);
return t[nod].go[lit];
}
int dict(int nod)
{
if(t[nod].dict!=-1)
return t[nod].dict;
if(nod==0)
{
t[nod].dict=0;
return t[nod].dict;
}
int nxt=suflink(nod);
if(t[nxt].leaf.size())
{
t[nod].dict=nxt;
return t[nod].dict;
}
t[nod].dict=dict(suflink(nod));
return t[nod].dict;
}
void getleaf(int nod)
{
use[nod]=1;
int nxt=dict(nod);
if(nxt==0)
return;
if(!use[nxt])
getleaf(nxt);
for(auto i:t[nxt].leaf)
t[nod].leaf.push_back(i);
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fout.tie(0);
fin>>a>>n;
emptynode.c='0';
emptynode.dict=-1;
emptynode.suflink=-1;
for(int i='a';i<='z';i++)
{
emptynode.muchii[i-'a'+1]=-1;
emptynode.go[i-'a'+1]=-1;
}
t.push_back(emptynode);
for(int i=1;i<=n;i++)
{
string x;
fin>>x;
add(x,i);
}
for(int i=1;i<t.size();i++)
getleaf(i);
int v=0;
for(auto c:a)
{
v=go(v,c);
for(auto i:t[v].leaf)
sol[i]++;
int aux=v;
/*while(dict(aux)>0)
{
aux=dict(aux);
for(auto i:t[aux].leaf)
sol[i]++;
}*/
}
for(int i=1;i<=n;i++)
fout<<sol[i]<<'\n';
return 0;
}