Pagini recente » Cod sursa (job #811883) | Cod sursa (job #2105387) | Cod sursa (job #847809) | Cod sursa (job #1601537) | Cod sursa (job #1508992)
#include <fstream>
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
struct Node {
int cnt, leg[27], bad;
vector<int> adj;
} T[200005];
int root = 1, nodes = 1;
int Where[105];
char Tx[1000005], P[10005];
int addWord(char str[]) {
int node = root;
for(int i=0; str[i]; i++) {
int c = str[i] - 'a';
if(T[node].leg[c] == 0) T[node].leg[c] = ++nodes;
node = T[node].leg[c];
}
return node;
}
void build_bad(int node, int parent, int c) {
if(node != root) {
int bad = T[parent].bad;
while(bad && T[bad].leg[c] == 0) bad = T[bad].bad;
T[node].bad = (bad) ? T[bad].leg[c] : root;
T[T[node].bad].adj.push_back(node);
}
for(c=0; c<='z'-'a'; c++)
if(T[node].leg[c])
build_bad(T[node].leg[c], node, c);
}
void solve(char str[]) {
int node = root;
for(int i=0; str[i]; i++) {
int c = str[i] - 'a';
while(node && T[node].leg[c] == 0) node = T[node].bad;
node = (node) ? T[node].leg[c] : root;
T[node].cnt += 1;
}
}
void dfs(int node) {
for(auto vec : T[node].adj)
dfs(vec), T[node].cnt += T[vec].cnt;
}
int main() {
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int n;
fin>>Tx>>n;
for(int i=1; i<=n; i++) {
fin>>P;
Where[i] = addWord(P);
}
build_bad(root, 0, 0);
solve(Tx);
dfs(root);
for(int i=1; i<=n; i++) {
fout<<T[Where[i]].cnt<<'\n';
}
}