Pagini recente » Cod sursa (job #2866301) | Cod sursa (job #1050918) | Cod sursa (job #2060249) | Istoria paginii runda/leulloe4 | Cod sursa (job #1563530)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#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;
int hits;
trieNode *son[30];
trieNode *suff;
trieNode()
{
pat.clear();
hits = 0;
suff = NULL;
memset(son, 0, sizeof(son));
}
} *root = new trieNode();
vector<trieNode*> antiBFS;
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;
antiBFS.push_back(root);
for (int i = 0; i < antiBFS.size(); i++) {
crt = antiBFS[i];
for (int i = 0; i < 26; i++)
if (crt->son[i]) {
crt->son[i]->suff = getSuff(crt, i);
antiBFS.push_back(crt->son[i]);
}
}
}
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)
{
crt->hits++;
if (!*p) return;
solve(findNode(crt, *p-'a'), p+1);
}
void prepare()
{
trieNode* crt;
for (int i = antiBFS.size()-1; i; --i) {
crt = antiBFS[i];
for (int i = 0, sz = crt->pat.size(); i < sz; i++)
sol[crt->pat[i]] += crt->hits;
crt->suff->hits += crt->hits;
}
}
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);
}
root->suff = root;
constructBounds();
solve(root, s);
prepare();
for (int i = 0; i < n; i++)
printf("%d\n", sol[i]);
return 0;
}