Pagini recente » Cod sursa (job #1974049) | Cod sursa (job #2877114) | Cod sursa (job #1085451) | Cod sursa (job #1938890) | Cod sursa (job #824861)
Cod sursa(job #824861)
#include <cstring>
#include <fstream>
#include <iostream>
#include <new>
#include <string>
#include <vector>
using namespace std;
struct node {
vector<int> index;
int cnt;
node * fail;
node * next[26];
};
node * root;
node * Q[26 * 100 * 10000];
int front, back;
int n;
string A, w;
int ans[101];
inline void bfs1() {
root->fail = root;
Q[back++] = root;
while (back - front > 0) {
node * u = Q[front++];
for (int i = 0; i < 26; i++) {
node * v = u->next[i];
if (v != 0) {
node * f = u->fail;
while (f != root && f->next[i] == 0) {
f = f->fail;
}
if (f->next[i] != 0 && f->next[i] != v) {
f = f->next[i];
}
v->fail = f;
Q[back++] = v;
}
}
}
}
inline void bfs2() {
while (back) {
node * u = Q[--back];
u->fail->cnt += u->cnt;
for (size_t i = 0; i < u->index.size(); i++) {
ans[u->index[i]] = u->cnt;
}
}
}
int main() {
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
cin >> A;
cin >> n;
root = new node();
node * current;
for (int i = 1; i <= n; i++) {
cin >> w;
current = root;
for (size_t j = 0; j < w.size(); j++) {
int c = w[j] - 'a';
if (current->next[c] == 0) {
current->next[c] = new node();
}
current = current->next[c];
}
current ->index.push_back(i);
}
bfs1();
current = root;
for (size_t i = 0; i < A.size(); i++) {
int c = A[i] - 'a';
while (current != root && current->next[c] == 0) {
current = current->fail;
}
if (current->next[c] != 0) {
current = current->next[c];
}
current->cnt++;
}
bfs2();
for (int i = 1; i <= n; i++) {
cout << ans[i] << endl;
}
return 0;
}