Pagini recente » Cod sursa (job #484532) | Cod sursa (job #484535) | Cod sursa (job #1340683) | Cod sursa (job #840741) | Cod sursa (job #1563254)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAXS 1000050
#define MAXN 150
#define MAXCUV 10050
using namespace std;
char s[MAXS], aux[MAXCUV];
int n, sol[MAXN];
struct trieNode
{
vector<int> pat;
trieNode *son[30];
trieNode *suff;
trieNode()
{
pat.clear();
suff = NULL;
memset(son, 0, sizeof(son));
}
} *root = new trieNode();
void addToTrie(char *p, int pattern, trieNode *crt = root)
{
if (!*p) {
crt->pat.push_back(pattern);
return;
}
if (crt->son[*p-'a'] == NULL)
crt->son[*p-'a'] = new trieNode();
addToTrie(p+1, pattern, crt->son[*p-'a']);
}
trieNode* getSuff(trieNode *crt, int ind)
{
if (crt == root)
return crt;
if (crt->suff->son[ind])
return crt->suff->son[ind];
return getSuff(crt->suff, ind);
}
void constructBounds(trieNode *crt)
{
if (crt == NULL)
return;
for (int i = 0; i < 26; i++)
if (crt->son[i]) {
crt->son[i]->suff = getSuff(crt, i);
constructBounds(crt->son[i]);
}
}
void updateSolution(trieNode *crt)
{
if (crt == root) return;
for (int i = 0; i < crt->pat.size(); i++)
sol[crt->pat[i]]++;
updateSolution(crt->suff);
}
trieNode* findNode(trieNode *crt, int ind)
{
if (crt->son[ind])
return crt->son[ind];
if (crt == root)
return crt;
return findNode(crt->suff, ind);
}
void solve(trieNode *crt, char *p)
{
updateSolution(crt);
if (!*p) return;
if (crt->son[*p-'a'])
solve(crt->son[*p-'a'], p+1);
else
solve(findNode(crt->suff, *p-'a'), p+1);
}
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
gets(s);
scanf("%d\n", &n);
for (int i = 0; i < n; i++) {
gets(aux);
addToTrie(aux, i);
}
constructBounds(root);
root->suff = root;
solve(root, s);
for (int i = 0; i < n; i++)
printf("%d\n", sol[i]);
return 0;
}