Pagini recente » Cod sursa (job #1895755) | Cod sursa (job #2075128) | Cod sursa (job #2777597) | Cod sursa (job #630381) | Cod sursa (job #1509018)
#include <cstdio>
using namespace std;
int Vec[1000005], Next[1000005], nodesx;
struct Node {
int cnt, leg[27], bad, adj, parent, c;
} T[1000005];
int root = 1, nodes = 1;
int Where[105];
char Tx[1000005], P[10005];
void addEdge(int a, int b) {
++nodesx;
Vec[nodesx] = b;
Next[nodesx] = T[a].adj;
T[a].adj = nodesx;
}
int addWord() {
int node = root;
for(int i=0; P[i]; i++) {
int c = P[i] - 'a';
if(T[node].leg[c] == 0) {
T[node].leg[c] = ++nodes;
T[nodes].parent = node;
T[nodes].c = c;
}
node = T[node].leg[c];
}
return node;
}
int Q[1000005], b, e;
void build_bad() {
Q[e++] = root;
while(b < e) {
int node = Q[b++];
if(node != root) {
int bad = T[T[node].parent].bad;
int c = T[node].c;
while(bad && T[bad].leg[c] == 0) bad = T[bad].bad;
T[node].bad = (bad) ? T[bad].leg[c] : root;
addEdge(T[node].bad, node);
}
for(int c=0; c<='z'-'a'; c++)
if(T[node].leg[c])
Q[e++] = T[node].leg[c];
}
}
void solve() {
int node = root;
for(int i=0; Tx[i]; i++) {
int c = Tx[i] - 'a';
while(node && T[node].leg[c] == 0) node = T[node].bad;
node = (node) ? T[node].leg[c] : root;
T[node].cnt++;
}
}
void dfs() {
e = 0;
Q[++e] = root;
while(e) {
int node = Q[e];
if(node < 0) {
e--, node = -node;
for(int i = T[node].adj; i; i = Next[i])
T[node].cnt += T[Vec[i]].cnt;
} else {
Q[e] = -Q[e];
for(int i = T[node].adj; i; i = Next[i])
Q[++e] = Vec[i];
}
}
}
int main() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
int n;
scanf("%s\n%d", &Tx, &n);
for(int i=1; i<=n; i++) {
scanf("%s", &P);
Where[i] = addWord();
}
build_bad();
solve();
dfs();
for(int i=1; i<=n; i++)
printf("%d\n", T[Where[i]].cnt);
}