Pagini recente » Cod sursa (job #1600328) | Cod sursa (job #32969) | Cod sursa (job #3277698) | Cod sursa (job #1235883) | Cod sursa (job #3257235)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e2;
string A[MAX + 3];
int N;
struct Nod{
int cnt;
Nod *fail;
Nod *nxt[28];
Nod *par;
int chr;
int dp;
Nod() {
cnt = 0;
dp = 0;
for(int i = 0; i < 26; i++) {
nxt[i] = NULL;
}
fail = NULL;
}
};
Nod *fnl[MAX + 3];
vector<Nod*>bfs;
int idx;
struct AhoCorasick{
Nod *root;
AhoCorasick() {
root = new Nod;
}
void insert(string &s) {
Nod *curr = root;
for(int i = 0; i < s.size(); i++) {
if(curr->nxt[s[i] - 'a'] == NULL) {
curr->nxt[s[i] - 'a'] = new Nod;
}
curr->nxt[s[i] - 'a']->par = curr;
curr->nxt[s[i] - 'a']->chr = s[i] - 'a';
curr = curr->nxt[s[i] - 'a'];
}
curr->cnt++;
fnl[idx] = curr;
}
Nod *fail(Nod *curr) {
if(curr->fail != NULL) {
return curr->fail;
}
if(curr == root || curr->par == root) return root;
Nod *ans = curr->par->fail;
while(ans != root && ans->nxt[curr->chr] == NULL) {
ans = ans->fail;
}
if(ans->nxt[curr->chr] != NULL)
return ans->nxt[curr->chr];
return ans;
}
// Nod parcurg(Nod * curr, int chr) {
// if(curr->nxt[chr] != NULL) return *curr->nxt[chr];
// if(curr == root) return *curr;
// Nod ans = *parcurg(fail(curr), chr);
// return *ans;
// }
void build() {
queue<Nod*>q;
q.push(root);
while(!q.empty()) {
bfs.push_back(q.front());
Nod *act = q.front();
act->fail = fail(act);
//cout << act->chr << ' ' << act->fail->chr << '\n';
for(int i = 0; i < 26; i++) {
if(act->nxt[i] != NULL) q.push(act->nxt[i]);
}
//act->dp = act->fail->dp + act->cnt;
q.pop();
}
}
}aho;
int main() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
string s;
cin >> s;
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> A[i];
idx = i;
aho.insert(A[i]);
}
//sort(A + 1, A + N + 1);
aho.build();
int ans = 0;
Nod *start = aho.root;
for(int i = 0; i < s.size(); i++) {
while(start->nxt[s[i] - 'a'] == NULL && start != aho.root) {
start = start->fail;
}
if(start->nxt[s[i] - 'a'] != NULL) {
start = start->nxt[s[i] - 'a'];
}
start->dp++;
}
reverse(bfs.begin(), bfs.end());
// for(auto i : bfs) {
// cout << i->dp << ' ' << i->chr << '\n';
// }
for(auto i : bfs){
//cout << (i->dp) << ' ';
i->fail->dp += i->dp;
}
for(int i = 1; i <= N; i++) {
cout << fnl[i]->dp << '\n';
}
//cout << ans;
}