Pagini recente » Cod sursa (job #8380) | Profil fetitele_powerpuff | Cod sursa (job #532949) | Cod sursa (job #231043) | Cod sursa (job #2137883)
#include <bits/stdc++.h>
using namespace std;
struct node{
node *next[30], *go[30], *papa, *link = 0;
int nr = 0, lastC;
node(node *papa, int lastC){
this->papa = papa;
this->lastC = lastC;
memset(next, 0, sizeof(next));
memset(go, 0, sizeof(go));
}
} *root = new node(0, ' ');
string text;
vector<node*> v;
node* words[102];
node* getLink(node *it);
node* go(node *it, int c){
if(it->go[c]) return it->go[c];
if(it->next[c]) return it->go[c] = it->next[c];
if(!it->papa) return it;
return it->go[c] = go(getLink(it), c);
}
node* getLink(node *it){
if(!it->papa) return it;
if(it->link) return it->link;
if(!it->papa->papa) return it->link = it->papa;
return it->link = go(getLink(it->papa), it->lastC);
}
void getNodesOrder(node *it){
for(auto next : it->next)
if(next) getNodesOrder(next);
v.push_back(it);
}
int main(){
// freopen("ac.in", "r", stdin);
cin >> text;
int n; cin >> n;
for(int i = 1; i <= n; i ++){
string s; cin >> s;
node *it = root;
for(auto c : s){
if(! it->next[c - 'a']) it->next[c - 'a'] = new node(it, c - 'a');
it = it->next[c - 'a'];
}
words[i] = it;
}
node *it = root;
for(auto c : text)
it = go(it, c - 'a'), it->nr ++;
v.push_back(root);
for(int i = 0; i < v.size(); i ++)
for(int c = 0; c <= 'z' - 'a'; c ++)
if(v[i]->next[c]) v.push_back(v[i]->next[c]);
reverse(v.begin(), v.end());
for(auto it : v){
node *next = getLink(it);
next->nr += it->nr;
}
for(int i = 1; i <= n; i ++)
cout << words[i]->nr << '\n';
cin >> n;
}