Pagini recente » Cod sursa (job #1568919) | Cod sursa (job #2748331) | Cod sursa (job #491585) | Cod sursa (job #3178834) | Cod sursa (job #3225387)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int go(int,int);
int getsuf(int);
int getdict(int);
string v;
int n,sol[105];
struct node
{
int lit;
int par;
int go[27];
int suflink;
int dictlink;
vector<int> who;
} emp;
vector<node> t;
void add(string s,int ind)
{
int me=0;
for(char c:s)
{
int lit=c-'a';
if(t[me].go[lit]==-1)
{
t[me].go[lit]=t.size();
int x=t.size();
t.push_back(emp);
t[x].par=me;
t[x].lit=lit;
}
me=t[me].go[lit];
}
t[me].who.push_back(ind);
}
int go(int me,int lit)
{
if(t[me].go[lit]!=-1)
return t[me].go[lit];
if(me==0)
return 0;
t[me].go[lit]=go(getsuf(me),lit);
return t[me].go[lit];
}
int getsuf(int me)
{
if(t[me].suflink!=-1)
return t[me].suflink;
if(me==0||t[me].par==0)
{
t[me].suflink=0;
return 0;
}
t[me].suflink=go(getsuf(t[me].par),t[me].lit);
return t[me].suflink;
}
int getdict(int me)
{
if(t[me].dictlink!=-1)
return t[me].dictlink;
if(getsuf(me)==0)
{
t[me].dictlink=0;
return 0;
}
int x=getsuf(me);
if(t[x].who.size()>0)
{
t[me].dictlink=x;
return x;
}
t[me].dictlink=getdict(x);
return t[me].dictlink;
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
emp.suflink=-1;
emp.dictlink=-1;
for(int i=0;i<=26;i++)
emp.go[i]=-1;
t.push_back(emp);
t[0].suflink=0;
t[0].dictlink=0;
fin>>v;
fin>>n;
for(int i=1;i<=n;i++)
{
string s;
fin>>s;
add(s,i);
}
int me=0;
for(char c:v)
{
int lit=c-'a';
me=go(me,lit);
int aux=me;
while(aux!=0)
{
for(int i:t[aux].who)
sol[i]++;
aux=getdict(aux);
}
}
for(int i=1;i<=n;i++)
fout<<sol[i]<<'\n';
return 0;
}