Pagini recente » Cod sursa (job #1885724) | Cod sursa (job #1732561) | Cod sursa (job #3343009) | Cod sursa (job #1288323) | Cod sursa (job #3331517)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
#define cin fin
#define cout fout
const int SG=26;
const int MAXN=2e5+10;
int n,m;
string s;
struct Trie{
Trie *f[SG];
int rez;
Trie *b;
Trie (){
for (int i=0;i<SG;++i) f[i]=nullptr;
rez=0;
b=nullptr;
}
}*root,*v[MAXN];
stack <Trie *> st;
Trie *update (string a){
Trie *trie=root;
for (int i=0;i<a.size ();++i){
int x=int (a[i]-'a');
if (trie->f[x]==nullptr){
trie->f[x]=new Trie;
}
trie=trie->f[x];
}
return trie;
}
void solve_backedge (Trie *trie, int i){
Trie *bcrt=trie->b;
while (bcrt!=root and bcrt->f[i]==nullptr)
bcrt=bcrt->b;
if (bcrt->f[i]!=nullptr and bcrt!=trie){
trie->f[i]->b=bcrt->f[i];
}
else{
trie->f[i]->b=root;
}
}
void get_backedges (){
queue <Trie *> q;
root->b=root;
q.push (root);
while (!q.empty ()){
Trie *trie=q.front ();
st.push (trie);
q.pop ();
for (int i=0;i<SG;++i){
if (trie->f[i]==nullptr) continue;
solve_backedge (trie, i);
q.push (trie->f[i]);
}
}
}
void solve (){
Trie *trie=root;
for (int i=0;i<m;++i){
int x=int (s[i]-'a');
while (trie!=root and trie->f[x]==nullptr)
trie=trie->b;
if (trie->f[x]){
trie=trie->f[x];
}
trie->rez++;
}
while (!st.empty ()){
trie=st.top ();
st.pop ();
trie->b->rez+=trie->rez;
}
}
signed main()
{
cin >>s;
m=s.size ();
cin >>n;
root=new Trie;
for (int i=1;i<=n;++i){
string a;
cin >>a;
v[i]=update (a);
}
get_backedges ();
solve ();
for (int i=1;i<=n;++i){
cout <<v[i]->rez<<'\n';
}
return 0;
}