Pagini recente » Cod sursa (job #2177445) | Cod sursa (job #941685) | Monitorul de evaluare | Cod sursa (job #2450464) | Cod sursa (job #2469086)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int MAX_SIZE = 1e6 + 100;
const int VOCAB = 26;
const int MAX_N = 100;
const int CUV_SIZE = 1e4 + 10;
int f[MAX_SIZE][VOCAB];
int fail[MAX_SIZE];
int p[MAX_SIZE];
int lch[MAX_SIZE];
int cnt[MAX_SIZE];
int next_id = 2;
char s[MAX_SIZE], cuv[CUV_SIZE];
int ix[MAX_N];
void calc_fail(int n) {
// cout << n << ' ' << fail[n] << endl;
for (int i = 0; i < VOCAB; i++)
if (f[n][i]) {
int u = f[n][i];
int suf = fail[n];
while (suf != 1 && !f[suf][i])
suf = fail[suf];
if (f[suf][i] && f[suf][i] != u)
suf = f[suf][i];
else
suf = 1;
fail[u] = suf;
calc_fail(u);
}
}
int main() {
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
int n;
cin >> s;
cin >> n;
// cout << "1: " << endl;
for (int n0 = 0; n0 < n; n0++) {
cin >> cuv;
int i = 1;
for (int pos = 0; cuv[pos]; pos++) {
if (!f[i][cuv[pos] - 'a']) {
// cout << next_id << ": ";
// for (int j = 0; j <= pos; j++)
// cout << cuv[j];
// cout << endl;
p[next_id] = i;
f[i][cuv[pos] - 'a'] = next_id++;
}
i = f[i][cuv[pos] - 'a'];
lch[i] = cuv[pos] - 'a';
}
ix[n0] = i;
}
fail[1] = 1;
calc_fail(1);
int i = 1;
for (int pos = 0; s[pos]; pos++) {
while (i != 1 && !f[i][s[pos] - 'a'])
i = fail[i];
if (f[i][s[pos] - 'a'])
i = f[i][s[pos] - 'a'];
cnt[i]++;
}
// for (int i = 1; i < next_id; i++)
// cout << i << " -fail-> " << fail[i] << endl;
// for (int i = 1; i < next_id; i++)
// cout << i << " -p-> " << p[i] << endl;
vector<int> ord;
ord.push_back(1);
i = 0;
while (i < ord.size()) {
for (int j = 0; j < VOCAB; j++)
if (f[ord[i]][j])
ord.push_back(f[ord[i]][j]);
i++;
}
for (int i = ord.size() - 1; i >= 0; i--) {
cnt[fail[ord[i]]] += cnt[ord[i]];
}
for (int i = 0; i < n; i++)
cout << cnt[ix[i]] << '\n';
return 0;
}