Pagini recente » Cod sursa (job #108602) | Cod sursa (job #623027) | Cod sursa (job #653711) | Cod sursa (job #2524254) | Cod sursa (job #2586896)
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
const int MAX_N = 1e5 + 10, ALPH = 30;
struct Automaton {
int ans[MAX_N], dp[MAX_N], p[MAX_N];
int link[MAX_N], cnt, to[MAX_N][ALPH];
int leaf[MAX_N];
vector<int> g[MAX_N];
Automaton() {
cnt = 1;
for(int i = 0; i < MAX_N; i ++) {
fill_n(to[i], ALPH, -1);
}
}
void add(string &s, int tme) {
int curr = 0;
for(auto it : s) {
int c = it - 'a';
if(to[curr][c] == -1) {
to[curr][c] = cnt ++;
}
curr = to[curr][c];
}
leaf[curr] = tme;
p[tme] = curr;
}
void pushLink() {
queue<int> q; q.push(0);
link[0] = -1;
while(!q.empty()) {
int curr = q.front(); q.pop();
for(int c = 0; c < 30; c ++) if(to[curr][c] != -1) {
int next = to[curr][c];
int l = link[curr];
while(l && to[l][c] == -1) {l = link[l];}
if(to[l][c] != -1) {l = to[l][c];}
link[next] = l;
q.push(next);
g[l].push_back(next);
}
}
}
void dfs(int x) {
for(auto it : g[x]) {
dfs(it);
dp[x] += dp[it];
}
}
void getAns(string &s) {
int curr = 0;
for(auto itc : s) {
int c = itc - 'a';
while(curr && to[curr][c] == -1) {curr = link[curr];}
if(to[curr][c] != -1) {curr = to[curr][c];}
dp[curr] ++;
}
dfs(0);
}
};
Automaton au;
string s;
signed main() {
//ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ofstream myfile;
myfile.open ("ahocorasick.out");
ifstream myFileIn;
myFileIn.open ("ahocorasick.in");
myFileIn >> s;
int n;
myFileIn >> n;
for(int i = 0; i < n; i ++) {
string x;
myFileIn >> x;
au.add(x, i);
}
au.pushLink();
au.getAns(s);
for(int i = 0; i < n; i ++) {
myfile << au.dp[au.p[i]] << endl;
}
return 0;
}