Pagini recente » Cod sursa (job #2794411) | Cod sursa (job #164648) | Cod sursa (job #2679024) | Cod sursa (job #377739) | Cod sursa (job #1117487)
#include <cstdio>
#include <cstring>
#include <string>
#define NMAX 1000005
#define LMAX 10005
#define HMAX 26
#define TMAX 1200005
#define KMAX 105
#define ll long long
using namespace std;
char A[NMAX], B[LMAX], words[KMAX][LMAX];
int n, r;
struct trie
{
ll res;
trie *children[HMAX], *fail;
trie()
{
res = 0;
memset(children, 0, sizeof(children));
fail = 0;
}
};
trie *T = new trie();
trie *Q[TMAX];
void insert(trie *node, char *s)
{
if (*s == '\n')
return ;
if (node -> children[*s - 'a'] == 0)
node -> children[*s - 'a'] = new trie();
insert(node -> children[*s - 'a'], s + 1);
}
void make_links()
{
Q[r = 1] = T;
for (int i = 1; i <= r; i++)
for (int j = 0; j < HMAX; j++)
if (Q[i] -> children[j])
{
Q[++r] = Q[i] -> children[j];
if (Q[i] != T)
{
trie *aux = Q[i] -> fail;
while (aux != T && aux -> children[j] == 0)
aux = aux -> fail;
if (aux -> children[j]) aux = aux -> children[j];
Q[r] -> fail = aux;
}
else
Q[r] -> fail = T;
}
}
void go(trie *node, char *s)
{
if (*s == '\n')
return ;
while (node != T && node -> children[*s -'a'] == 0)
node = node -> fail;
if (node -> children[*s - 'a']) node = node -> children[*s - 'a'];
node -> res++;
go(node, s + 1);
}
void update()
{
Q[r = 1] = T;
for (int i = 1; i <= r; i++)
for (int j = 0; j < HMAX; j++)
if (Q[i] -> children[j])
Q[++r] = Q[i] -> children[j];
for (int i = r; i > 1; i--)
Q[i] -> fail -> res += Q[i] -> res;
}
ll get_res(trie *node, char *s)
{
if (*s == '\n')
return node -> res;
return get_res(node -> children[*s - 'a'], s + 1);
}
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
fgets(A + 1, NMAX, stdin);
scanf("%d\n", &n);
for (int i = 1; i <= n; i++)
{
fgets(B + 1, LMAX, stdin);
insert(T, B + 1);
memcpy(words[i], B, sizeof(B));
}
make_links();
go(T, A + 1);
update();
for (int i = 1; i <= n; i++)
printf("%lld\n", get_res(T, words[i] + 1));
return 0;
}