Pagini recente » Cod sursa (job #1177475) | Cod sursa (job #813831) | Cod sursa (job #394572) | Cod sursa (job #1243198) | Cod sursa (job #868700)
Cod sursa(job #868700)
#include <cstdio>
#include <cstring>
using namespace std;
#define maxl 1000010
#define maxs 10010
#define maxt 100010
#define sigma 27
#define maxn 110
int n, nn, m, lg, lp;
int q[maxt], sol[maxn], where[maxn];
struct trie
{
int nap, up, f[sigma];
} t[maxt];
char p[maxl], sc[maxs];
int add()
{
lg=strlen(sc);
int nc=1;
for(int i=0; i<lg; ++i)
{
sc[i]-='a';
if(t[nc].f[sc[i]]==0)
t[nc].f[sc[i]]=++nn;
nc=t[nc].f[sc[i]];
sc[i]=0;
}
return nc;
}
void bfs(int nc)
{
int q0=1, fiu, aux;
q[q0]=nc;
t[1].up=1;
for(int i=1; i<=q0; ++i)
{
nc=q[i];
for(int j=0; j<sigma; ++j)
{
if(t[nc].f[j]==0)
continue;
aux=t[nc].up;
while(aux!=1 && t[aux].f[j]==0)
aux=t[aux].up;
if(t[aux].f[j]!=0 && t[aux].f[j]!=t[nc].f[j])
aux=t[aux].f[j];
q[++q0]=t[nc].f[j];
t[t[nc].f[j]].up=aux;
}
}
}
void solve()
{
int nc=1;
char cc;
for(int i=0; i<lp; ++i)
{
cc=p[i]-'a';
while(t[nc].f[cc]==0 && nc>1)
nc=t[nc].up;
if(t[nc].f[cc]!=0)
nc=t[nc].f[cc];
++t[nc].nap;
}
for(int i=nn; i>1; --i)
{
nc=q[i];
t[t[nc].up].nap+=t[nc].nap;
}
for(int i=1; i<=n; ++i)
sol[i]=t[where[i]].nap;
}
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
scanf("%s", p);
lp=strlen(p);
nn=1;
scanf("%d\n", &n);
for(int i=1; i<=n; ++i)
{
scanf("%s", sc);
where[i]=add();lg=strlen(sc);
}
bfs(1);
solve();
for(int i=1; i<=n; ++i)
printf("%d\n", sol[i]);
return 0;
}