Pagini recente » Cod sursa (job #1232970) | Cod sursa (job #1635373) | Cod sursa (job #1508275) | Cod sursa (job #9342) | Cod sursa (job #1964862)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
const int maxA = 1000003;
const int maxC = 10003;
const int maxN = 103;
const int alf = 26;
int n;
int g[maxC*maxN][alf];
int tim=1;
int f[maxC*maxN];
int viz[maxC*maxN];
vector<int> poz[maxC*maxN];
string st;
string words[maxC];
stack<int> antib;
int ans[maxC];
void ins(string &s, int i, int cstate, int val) {
while(i != s.size()) {
if(g[cstate][s[i]-'a'] == 0)
g[cstate][s[i]-'a'] = ++tim;
cstate = g[cstate][s[i]-'a'];
i++;
}
poz[cstate].push_back(val);
}
void bfs() {
queue<int> q;
for(int i = 0; i < alf; i++) {
if(g[1][i] != 0) {
f[g[1][i]] = 1;
q.push(g[1][i]);
} else
g[1][i] = 1;
}
f[1] = 1;
int cstate;
while(!q.empty()) {
cstate = q.front();
antib.push(cstate);
q.pop();
for(int i = 0; i < 26; i++) {
if(g[cstate][i] != 0 && g[cstate][i] != 1) {
int F = f[cstate];
while(g[F][i] == 0)
F = f[F];
f[g[cstate][i]] = g[F][i];
q.push(g[cstate][i]);
}
}
}
}
void dfs(int cstate, int p) {
while(p != st.size()) {
viz[cstate]++;
while(g[cstate][st[p]-'a'] == 0)
cstate = f[cstate];
cstate = g[cstate][st[p]-'a'];
p++;
}
viz[cstate]++;
}
void antibfs() {
int crr;
while(!antib.empty()) {
crr = antib.top();
antib.pop();
for(int i = 0; i < poz[crr].size(); i++)
ans[poz[crr][i]] = viz[crr];
viz[f[crr]] += viz[crr];
}
}
int main() {
in >> st;
in >> n;
for(int i = 1; i <= n; i++) {
in >> words[i];
ins(words[i], 0, 1, i);
}
bfs();
dfs(1, 0);
antibfs();
for(int i = 1; i <= n; i++)
out << ans[i] << '\n';
return 0;
}