Pagini recente » Cod sursa (job #2118337) | Cod sursa (job #3228377) | Cod sursa (job #389343) | Cod sursa (job #386256) | Cod sursa (job #2645553)
#include <bits/stdc++.h>
using namespace std;
const int D = 27;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
vector<int> us, Q;
struct Vertex {
int f, link;
vector<int> nxt;
Vertex() {
f = 0, link;
nxt.assign(D, -1);
}
};
struct AC {
vector<Vertex> trie;
AC() {
trie.resize(1);
}
void insert(string &s) {
int node = 0;
for(char c : s) {
int x = c - 'a';
if(trie[node].nxt[x] == -1) {
trie[node].nxt[x] = trie.size();
trie.emplace_back();
}
node = trie[node].nxt[x];
}
us.push_back(node);
}
void build() {
Q.push_back(0);
trie[0].link = 0;
for(int i = 0; i < Q.size(); i++) {
int node = Q[i];
for(int x = 0; x < D; x++) {
if (trie[node].nxt[x] == -1) continue;
int now = trie[node].link;
while(now && trie[now].nxt[x] == -1) now = trie[now].link;
if(trie[now].nxt[x] != -1 && trie[now].nxt[x] != trie[node].nxt[x]) {
now = trie[now].nxt[x];
}
Q.push_back(trie[node].nxt[x]);
trie[trie[node].nxt[x]].link = now;
}
}
}
void get_ans(string &me) {
int node = 0;
for(char c : me) {
int x = c - 'a';
while(trie[node].nxt[x] == -1 && node) {
node = trie[node].link;
}
if(trie[node].nxt[x] != -1) {
node = trie[node].nxt[x];
}
//cout << node << '\n';
trie[node].f += 1;
}
for(int i = Q.size() - 1; i >= 0; i--) {
trie[trie[Q[i]].link].f += trie[Q[i]].f;
}
for(auto it : us) {
out << trie[it].f << '\n';
}
}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
string t;
in >> t;
int n;
in >> n;
AC aho;
for(int i = 0; i < n; i++) {
string s;
in >> s;
aho.insert(s);
}
aho.build();
aho.get_ans(t);
return 0;
}