Pagini recente » Cod sursa (job #2810212) | Cod sursa (job #3252090) | Cod sursa (job #2430459) | Cod sursa (job #2096649) | Cod sursa (job #2404208)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <ctime>
#include <unordered_map>
#include <iomanip>
#include <complex>
#include <cassert>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define deb(a) cerr<< #a << "= " << (a)<<"\n";
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef complex<double> base;
typedef vector<int> vi;
typedef pair<int,int> pii;
template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream; }
ll fpow(ll x, ll p, ll m){ll r=1; for (;p;p>>=1){ if (p&1) r=r*x%m; x=x*x%m; } return r;}
ll inv(ll a, ll b){ return a<2 ? a : ((a-inv(b%a,a))*b+1)/a%b; }
int gcd(int a, int b){ if (!b) return a; return gcd(b,a%b);}
ll gcd(ll a, ll b){ if (!b) return a; return gcd(b,a%b);}
int N,t[1000010][26],T=1,fail[1000010],cnt[1000010],pos[110];
string s,a[110];
vi q;
int ins(int nod, string &s, int p, int ind){
if (nod==0) nod=++T;
if (p==(int)s.length()){
pos[ind]=nod;
return nod;
}
t[nod][s[p]-'a'] = ins(t[nod][s[p]-'a'],s,p+1,ind);
return nod;
}
void bfs(){
q = {1};
fail[1] = 1;
for (int i=0; i<(int)q.size(); i++){
int cr=q[i];
for (int j=0; j<26; j++)
if (t[cr][j]){
int f = fail[cr];
while (f!=1 && t[f][j]==0)
f=fail[f];
if (t[f][j] && t[f][j]!=t[cr][j])
fail[t[cr][j]]=t[f][j];
else fail[t[cr][j]]=1;
q.pb(t[cr][j]);
}
}
}
void antibfs(){
for (int i=(int)q.size()-1; i>=0; i--){
cnt[fail[q[i]]]+=cnt[q[i]];
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
cin >> s;
cin >> N;
int i;
for (i=1; i<=N; i++){
cin >> a[i];
ins(1,a[i],0,i);
}
bfs();
int cr=1;
for (i=0; i<(int)s.length(); i++){
while (cr!=1 && !t[cr][s[i]-'a'])
cr=fail[cr];
if (t[cr][s[i]-'a'])
cr=t[cr][s[i]-'a'];
cnt[cr]++;
}
antibfs();
for (i=1; i<=N; i++)
cout << cnt[pos[i]] << "\n";
}