Pagini recente » Cod sursa (job #833240) | Cod sursa (job #2740260) | Cod sursa (job #1317608) | Cod sursa (job #2692878) | Cod sursa (job #2587106)
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;
const int mod=1e9+7;
const int modu=1999999973;
const int modul=998244353;
int n;
string s,t[105];
map<string,int>ans;
struct Trie{
int val,parinte,trail;
vector<string>cont;
int a[27];
Trie(){
val = parinte = trail=0;
for(int i=0;i<=25;i++) a[i]=0;
}
}tz;
vector<Trie>vecc;
void buildtrie(){
vecc.push_back(tz);
for(int i=1;i<=n;i++){
int curr=0;
for(int j=0;j<t[i].size();j++){
if(vecc[curr].a[t[i][j]-'a']){
curr=vecc[curr].a[t[i][j]-'a'];
}
else{
vecc[curr].a[t[i][j]-'a']=vecc.size();
vecc.push_back(tz);
vecc[vecc.size()-1].val=(t[i][j]-'a');
vecc[vecc.size()-1].parinte=curr;
curr=vecc.size()-1;
}
if(j==(t[i].size()-1)) vecc[curr].cont.push_back(t[i]);
}
}
}
void bfs(){
queue<int>q;
q.push(0);
bitset<260000>viz;
viz[0]=1;
while(q.size()){
int x=q.front();
if(x>=1){
int v=vecc[x].val;
int y=vecc[vecc[x].parinte].trail;
if(vecc[x].parinte!=0)while(true){
if(vecc[y].a[v]>0){
vecc[x].trail=vecc[y].a[v];
for(int i=0;i<vecc[vecc[y].a[v]].cont.size();i++){
vecc[x].cont.push_back(vecc[vecc[y].a[v]].cont[i]);
}
break;
}
if(vecc[y].trail==y) break;
y=vecc[y].trail;
}
}
for(int i=0;i<=25;i++){
if(vecc[x].a[i]>=1 && viz[vecc[x].a[i]]==0){
q.push(vecc[x].a[i]);
viz[vecc[x].a[i]]=1;
}
}
q.pop();
}
return;
}
void calc(){
int indx=0;
for(int i=0;i<s.size();i++){
if(vecc[indx].a[s[i]-'a']){
indx=vecc[indx].a[s[i]-'a'];
for(int j=0;j<vecc[indx].cont.size();j++){
ans[vecc[indx].cont[j]]++;
}
}
else{
while(true){
if(indx==vecc[indx].trail) break;
indx=vecc[indx].trail;
if(vecc[indx].a[s[i]-'a']){
indx=vecc[indx].a[s[i]-'a'];
for(int j=0;j<vecc[indx].cont.size();j++){
ans[vecc[indx].cont[j]]++;
}
break;
}
}
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
srand(chrono::steady_clock::now().time_since_epoch().count());
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
cin >> s >> n;
for(int i=1;i<=n;i++){
cin >> t[i];
}
buildtrie();
bfs();
calc();
for(int i=1;i<=n;i++) cout << ans[t[i]] << '\n';
}