Pagini recente » Cod sursa (job #1730034) | Cod sursa (job #2322564) | Cod sursa (job #3319279) | Cod sursa (job #316158) | Cod sursa (job #3357828)
#include <vector>
#include <algorithm>
#include <queue>
#include <fstream>
using namespace std;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
string S;
int n;
string s[110];
void citire() {
cin >> S;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
}
}
const int lit = 'z' - 'a' + 1;
struct nod {
int nxt[lit], fail, val;
nod() {
for (int i = 0; i < lit; i++) nxt[i] = 0;
fail = 0;
val = 0;
}
} v[1000100];
int pnt = 0;
int fin[110];
void trie(int nod, int sir, int lv) {
if (lv == (int)s[sir].size()) {
fin[sir] = nod;
return;
}
int c = s[sir][lv] - 'a';
if (!v[nod].nxt[c]) {
v[nod].nxt[c] = ++pnt;
}
trie(v[nod].nxt[c], sir, lv + 1);
}
queue<int> q;
void fail() {
for (int i = 0; i < lit; i++) {
if (v[0].nxt[i]) {
v[v[0].nxt[i]].fail = 0;
q.push(v[0].nxt[i]);
}
}
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = 0; i < lit; i++) {
if (v[now].nxt[i]) {
int child = v[now].nxt[i];
int f = v[now].fail;
while (f && !v[f].nxt[i]) {
f = v[f].fail;
}
if (v[f].nxt[i]) {
f = v[f].nxt[i];
}
v[child].fail = f;
q.push(child);
}
}
}
}
void val() {
int now = 0;
for (int i = 0; i < (int)S.size(); i++) {
int c = S[i] - 'a';
while (now && !v[now].nxt[c]) {
now = v[now].fail;
}
if (v[now].nxt[c]) {
now = v[now].nxt[c];
}
v[now].val++;
}
}
void prop() {
vector<int> ord;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
ord.push_back(u);
for (int i = 0; i < lit; i++) {
if (v[u].nxt[i]) {
q.push(v[u].nxt[i]);
}
}
}
reverse(ord.begin(), ord.end());
for (int u : ord) {
if (v[u].fail) {
v[v[u].fail].val += v[u].val;
}
}
}
int main() {
citire();
for (int i = 1; i <= n; i++) {
trie(0, i, 0);
}
fail();
val();
prop();
for (int i = 1; i <= n; i++) {
cout << v[fin[i]].val << '\n';
}
return 0;
}