Pagini recente » Istoria paginii runda/winners21 | Istoria paginii runda/0931011001 | Istoria paginii runda/23dezile_4/clasament | Cod sursa (job #733581) | Cod sursa (job #1705177)
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
const int MAXN = 300005;
typedef tree<
char,
int,
less<char>,
ov_tree_tag,
null_node_update>
ordered_set;
struct AhoCorasick {
struct Node {
int cnt, bad, adj, parent;
char c;
unordered_map<char, int> leg;
};
vector<Node> T;
int root = 1, nodes = 1;
AhoCorasick(int sz) {
T.resize(sz);
}
int addWord(const string &word) {
int node = root;
for(auto c : word) {
auto &nxt = T[node].leg[c];
if(nxt == 0) {
nxt = ++nodes;
T[nodes].parent = node;
T[nodes].c = c;
}
node = nxt;
}
return node;
}
queue<int> Q;
void buildBad() {
Q.push(root);
while(!Q.empty()) {
int node = Q.front();
Q.pop();
int bad = T[T[node].parent].bad;
char c = T[node].c;
while(bad && T[bad].leg.find(c) == T[bad].leg.end())
bad = T[bad].bad;
T[node].bad = (node == root) ? 0 : (bad) ? T[bad].leg[c] : root;
for(auto p : T[node].leg)
Q.push(p.second);
}
}
vector<int> Deg, Sol;
void parseText(const string &text) {
int node = root;
Sol.resize(nodes + 1);
for(auto c : text) {
while(node && T[node].leg.find(c) == T[node].leg.end())
node = T[node].bad;
node = node ? T[node].leg[c] : root;
assert(node > 0);
Sol[node] += 1;
}
}
void dfs() {
Deg.resize(nodes + 1);
for(int i = 2; i <= nodes; ++i)
Deg[T[i].bad] += 1;
for(int i = 1; i <= nodes; ++i)
if(Deg[i] == 0)
Q.push(i);
while(!Q.empty()) {
int node = Q.front();
Q.pop();
Sol[T[node].bad] += Sol[node];
if(--Deg[T[node].bad] == 0)
Q.push(T[node].bad);
}
}
};
AhoCorasick A(MAXN);
string text, word;
vector<int> Where;
int main() {
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
int n;
cin >> text;
cin >> n;
Where.resize(n);
for(int i = 0; i < n; ++i) {
cin >> word;
Where[i] = A.addWord(word);
}
A.buildBad();
A.parseText(text);
A.dfs();
for(auto q : Where) {
cout << A.Sol[q] << '\n';
}
return 0;
}