Pagini recente » Istoria paginii runda/fgdgd/clasament | Istoria paginii runda/runda1-uoc | Cod sursa (job #1243505) | Istoria paginii runda/tema123 | Cod sursa (job #1705147)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
struct AhoCorasick {
struct Node {
int cnt, bad, adj, parent;
char c;
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.count(c) == 0)
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);
}
for(int i = 1; i <= nodes; ++i)
cerr << T[i].bad << " ";
cerr << endl;
}
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.count(c) == 0)
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() {
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;
}