Pagini recente » Cod sursa (job #1975367) | Cod sursa (job #2505481) | Cod sursa (job #3278268) | Cod sursa (job #864916) | Cod sursa (job #3257236)
#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;
}
void build() {
queue<Nod*>q;
q.push(root);
while(!q.empty()) {
bfs.push_back(q.front());
Nod *act = q.front();
act->fail = fail(act);
for(int i = 0; i < 26; i++) {
if(act->nxt[i] != NULL) q.push(act->nxt[i]);
}
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]);
}
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){
i->fail->dp += i->dp;
}
for(int i = 1; i <= N; i++) {
cout << fnl[i]->dp << '\n';
}
}