Pagini recente » Cod sursa (job #1218082) | Cod sursa (job #3126766) | Cod sursa (job #1270116) | Cod sursa (job #3285819) | Cod sursa (job #3255553)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
#define Nmax 2000100
int N;
string s, t;
vi cnt, v;
class Aho {
public:
static const int sigma = 26; // alphabet size
static const int off = 'a'; // first letter
int nodes; // nodes
int NR = 0; // terminal nodes
vi tr; //
vi term; //
vi link; // fail edge
vvi to; // edges
// custom shite
vi ind; // index of string that ends here
Aho() {
nodes = 1;
_new_node_update();
}
void _new_node_update() {
tr.pb(0);
term.pb(0);
link.pb(0);
to.pb(vi(sigma, 0));
ind.pb(0); // custom
}
void add(string &s, int val) {
int cur = 0; // root
for(auto c: s) {
if(!to[cur][c - off]) {
to[cur][c - off] = nodes++;
_new_node_update();
}
cur = to[cur][c - off];
}
term[cur] = cur;
tr[cur] = ++NR;
// custom shite
if(ind[cur] == 0) {
ind[cur] = val;
} else {
v[val] = ind[cur];
}
}
void push_links() {
queue<int> Q;
Q.push(0);
while(!Q.empty()) {
int V = Q.front();
Q.pop();
int U = link[V];
if(!term[V]) term[V] = term[U];
FOR(c, sigma) {
if(to[V][c]) {
link[to[V][c]] = V ? to[U][c] : 0;
Q.push(to[V][c]);
} else {
to[V][c] = to[U][c];
}
}
}
}
void process_match(int node) {
++cnt[ind[node]];
}
void match(string &s) {
int cur = 0;
for(auto c: s) {
cur = to[cur][c-off];
int f = cur;
while(f) {
if(tr[f]) {
process_match(f);
}
if(f == term[f]) f = term[link[f]];
else f = term[f];
}
}
}
};
Aho aho;
int main() {
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
cin>>s>>N;
cnt.resize(N+1);
v.resize(N+1);
FOR(i, N+1) v[i] = i;
FOR(i,N) {
cin>>t;
aho.add(t, i+1);
}
aho.push_links();
aho.match(s);
for(int i=1;i<=N;++i) cout<<cnt[v[i]]<<"\n";
}