Pagini recente » Cod sursa (job #1226672) | Cod sursa (job #1205975) | Cod sursa (job #556163) | Cod sursa (job #1099553) | Cod sursa (job #2845351)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int kN = 100;
const int kSigma = 26;
struct node {
int dp;
vector<int> indexes;
node* nxt[kSigma];
node* failLink;
node() : dp(0), failLink(nullptr) {
for (int c = 0; c < kSigma; ++c) {
nxt[c] = nullptr;
}
}
};
string A, s;
vector<node*> order;
int sol[kN];
void ins(node* root, int ptr, int index) {
if (ptr == (int)s.size()) {
root->indexes.emplace_back(index);
return;
}
int c = s[ptr] - 'a';
if (!root->nxt[c]) {
root->nxt[c] = new node;
}
ins(root->nxt[c], ptr + 1, index);
}
void buildAho(node* root) {
root->failLink = root;
queue<node*> q;
for (int c = 0; c < kSigma; ++c) {
if (root->nxt[c]) {
node* v = root->nxt[c];
v->failLink = root;
q.emplace(v);
}
}
while (!q.empty()) {
node* u = q.front();
q.pop();
order.emplace_back(u);
for (int c = 0; c < kSigma; ++c) {
if (u->nxt[c]) {
node* v = u->nxt[c];
node* tmp = u->failLink;
while (!tmp->nxt[c] && tmp != root) {
tmp = tmp->failLink;
}
if (tmp->nxt[c]) {
v->failLink = tmp->nxt[c];
} else {
v->failLink = root;
}
q.emplace(v);
}
}
}
}
void makeCount(node* root) {
node* u = root;
for (size_t i = 0; i < A.size(); ++i) {
int c = A[i] - 'a';
while (!u->nxt[c] && u != root) {
u = u->failLink;
}
if (u->nxt[c]) {
u = u->nxt[c];
}
u->dp += 1;
}
reverse(order.begin(), order.end());
for (auto it : order) {
it->failLink->dp += it->dp;
for (int index : it->indexes) {
sol[index] = it->dp;
}
}
}
void testCase() {
fin >> A;
int n;
fin >> n;
node* root = new node;
for (int i = 0; i < n; ++i) {
fin >> s;
ins(root, 0, i);
}
buildAho(root);
makeCount(root);
for (int i = 0; i < n; ++i) {
fout << sol[i] << '\n';
}
}
int main() {
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
fin.close();
fout.close();
return 0;
}