Pagini recente » Cod sursa (job #1015302) | Cod sursa (job #1777125) | Cod sursa (job #683209) | Cod sursa (job #486161) | Cod sursa (job #2137289)
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using pii = pair<int, int>;
#define dbg(x) cerr<<#x": "<<(x)<<'\n'
#define dbg_v(x, n) {cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<(x)[_]<<' ';cerr<<'\n';}
#define all(v) v.begin(), v.end()
#define INF 2000000010
#define MOD 1000000007
#define ST_SIZE 1048600
#define QMAX
#define SMAX 1000010
#define NMAX 110
#define LMAX 10010
#define SIGMA 26
struct info {
int cnt;
char ch;
info *fth, *link;
info *next[SIGMA], *go[SIGMA];
info(info *_fth, char _ch) {
cnt = 0;
ch = _ch;
fth = _fth;
link = nullptr;
memset(next, 0, sizeof next);
memset(go, 0, sizeof(go));
}
};
char a[SMAX];
char s[NMAX][LMAX];
void add(info *node, char *s) {
if(!(*s)) return;
if(!node->next[*s - 'a']) node->next[*s - 'a'] = new info(node, *s);
add(node->next[*s - 'a'], s + 1);
}
int getCnt(info *node, char *s) {
for(; *s; ++s) node = node->next[*s - 'a'];
return node->cnt;
}
info* getLink(info *node);
info* go(info *node, char ch);
void bfs(info *root);
void print(info *node, char ch, string indent = "") {
cout << indent << ' ' << ch << ' ' << node->cnt << '\n';
for(int i = 0; i < SIGMA; ++i)
if(node->next[i])
print(node->next[i], 'a' + i, indent + '\t');
}
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
int i, n;
info *root, *node;
root = new info(nullptr, 0);
scanf("%s", a);
scanf(" %d", &n);
for(i = 0; i < n; ++i) {
scanf(" %s", s[i]);
add(root, s[i]);
}
for(node = root, i = 0; a[i]; ++i) {
node = go(node, a[i]);
++node->cnt;
}
//print(root, 0);
bfs(root);
//print(root, 0);
for(i = 0; i < n; ++i)
printf("%d\n", getCnt(root, s[i]));
return 0;
}
info* getLink(info *node) {
if(!node->fth) return node;
if(!node->fth->fth) return node->fth;
if(node->link) return node->link;
return node->link = go(getLink(node->fth), node->ch);
}
info* go(info *node, char ch) {
if(node->next[ch - 'a']) return node->next[ch - 'a'];
if(node->go[ch - 'a']) return node->go[ch - 'a'];
if(!node->fth) return node;
return node->go[ch - 'a'] = go(getLink(node), ch);
}
void bfs(info *root) {
int i, l;
vector<info*> Q;
for(Q.push_back(root), l = 0; l < Q.size(); ++l) {
for(i = 0; i < SIGMA; ++i)
if(Q[l]->next[i])
Q.push_back(Q[l]->next[i]);
}
for(i = (int) Q.size() - 1; i > 0; --i)
getLink(Q[i])->cnt += Q[i]->cnt;
}