Pagini recente » Cod sursa (job #668903) | Cod sursa (job #2594236) | Cod sursa (job #507182) | Cod sursa (job #2441596) | Cod sursa (job #1981542)
#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 10100
#define inf 101010000
#define sigma 26
int tr[Nmax], nw[Nmax], NR, term[Nmax], len[Nmax], to[Nmax][sigma], link[Nmax], sz = 1;
map<string,int> h;
void add(string s) {
if(h[s]) return;
int cur = 0;
for(auto c: s) {
if(!to[cur][c - 'a']) {
to[cur][c - 'a'] = sz++;
len[to[cur][c - 'a']] = len[cur] + 1;
}
cur = to[cur][c - 'a'];
}
term[cur] = cur;
tr[cur] = ++NR;
h[s]=NR;
}
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(int c = 0; c < sigma; c++) {
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];
}
}
}
}
string S[Nmax];
int rv[Nmax];
int main() { //6AM8-8R6M-F38B-7CY9-RF6K
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
string s;
fin >> s;
int N;
fin >> N;
FOR(i,N) {
string s1;
fin >> S[i];
add(S[i]);
}
push_links();
int cur = 0;
for(auto c : s) {
cur = to[cur][c-'a'];
int f = cur;
while(f) {
// cout << f << endl;
if(tr[f]) ++rv[tr[f]];
f = link[f];
}
//cout << rv[1] << " ";
}
FOR(i,N) fout << rv[h[S[i]]] << "\n";
}