Pagini recente » Cod sursa (job #2289521) | Cod sursa (job #2744823) | Cod sursa (job #2165634) | Cod sursa (job #3210722) | Cod sursa (job #2431991)
//ALEX ENACHE
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
//#include <iostream>
#include <fstream>
ifstream cin ("ahocorasick.in");ofstream cout ("ahocorasick.out");
string S;
int n;
string s[110];
void citire (){
cin>>S;
cin>>n;
for (int i=1; i<=n; i++){
cin>>s[i];
}
}
const int lit = 'z'-'a'+1;
struct nod{
int nxt[lit] , fail , val;
//string s;
} v[1000100];
int pnt = 0;
int fin[110];
void trie (int nod , int sir , int lv){
if (lv == s[sir].size()){ fin[sir]=nod; return; }
if (!v[nod].nxt[s[sir][lv]-'a']){ v[nod].nxt[s[sir][lv]-'a'] = ++pnt; }
trie (v[nod].nxt[s[sir][lv]-'a'] , sir , lv+1);
}
queue < int > q;
vector < int > ord;
void fail (){
for (int i=0; i<lit; i++){
if (v[0].nxt[i]){
q.push(v[0].nxt[i]);
//v[v[0].nxt[i]].s = char(i+'a');
}
}
while (!q.empty()){
int now = q.front();
//cout<<v[now].s<<" "<<v[v[now].fail].s<<'\n';
ord.push_back(now);
q.pop();
for (int i=0; i<lit; i++){
if (v[now].nxt[i]){
int cop = v[now].nxt[i];
q.push(cop);
//v[cop].s = v[now].s + char(i+'a');
v[cop].fail = v[now].fail;
while (v[cop].fail && !v[v[cop].fail].nxt[i]){
v[cop].fail = v[v[cop].fail].fail;
}
if (v[v[cop].fail].nxt[i]){
v[cop].fail = v[v[cop].fail].nxt[i];
}
}
}
}
}
void val (){
int now = 0;
for (int i=0; i<S.size(); i++){
while (now && !v[now].nxt[S[i]-'a']){ now = v[now].fail; }
if (v[now].nxt[S[i]-'a']){ now = v[now].nxt[S[i]-'a']; }
v[now].val++;
//cout<<v[now].s<<" ";
}
//cout<<'\n';
}
void prop (){
reverse (ord.begin() , ord.end());
for (auto &x : ord){ v[v[x].fail].val += v[x].val; }
}
int main() {
//freopen("input", "r", stdin);freopen("output", "w", stdout);
citire();
for (int i=1; i<=n; i++){
trie (0 , i , 0);
}
fail();
val();
prop();
for (int i=1; i<=n; i++){
cout<<v[fin[i]].val<<'\n';
}
return 0;
}