Pagini recente » Cod sursa (job #1733835) | Cod sursa (job #243838) | Cod sursa (job #2052633) | Cod sursa (job #3288403) | Cod sursa (job #2469039)
#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) {
fail[n] = fail[p[n]];
// cout << n << ' ' << fail[n] << endl;
while (fail[n] != 1 && !f[fail[n]][lch[n]])
fail[n] = fail[fail[n]];
if (n != 1 && f[fail[n]][lch[n]])
fail[n] = f[fail[n]][lch[n]];
if (fail[n] == n)
fail[n] = 1;
for (int i = 0; i < VOCAB; i++)
if (f[n][i])
calc_fail(f[n][i]);
}
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[0] = 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;
}