Pagini recente » Cod sursa (job #707972) | Cod sursa (job #961374) | Cod sursa (job #1145360) | Cod sursa (job #62779) | Cod sursa (job #758460)
Cod sursa(job #758460)
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <utility>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define pii pair< int, int >
#define pdd pair< double, double >
template< typename T >
inline T minim(const T x, const T y) {
return ((x < y) ? x : y);
}
template< typename T >
inline T maxim(const T x, const T y) {
return ((x > y) ? x : y);
}
#define NA 26 // dimensiune alfabet
#define LA 1000010 // lungime sir A
#define LW 10010 // lungime cuvant
#define N 110 // nr de cuvinte
struct Node {
Node* son[NA];
vector< int > words;
int nr;
Node* fail;
Node() {
memset(son, 0, sizeof(son));
nr = 0;
}
};
char a[LA];
int n;
Node* T;
vector< Node* > q;
int rez[N];
void ins(Node* node, char const* p, const int& i) {
int nSon;
if (*p == '\0') {
node -> words.pb(i);
return;
}
nSon = int(*p - 'a');
if (node -> son[nSon] == NULL) {
node -> son[nSon] = new Node;
}
ins(node -> son[nSon], p + 1, i);
}
inline void bfs() {
Node* now;
Node* next;
Node* node;
q.pb(T);
T -> fail = T;
for (size_t i = 0; i < q.size(); ++i) {
now = q[i];
for (int j = 0; j < NA; ++j) {
if (now -> son[j] == NULL) {
continue;
}
next = now -> son[j];
for (node = now -> fail; node != T && node -> son[j] == NULL; node = node -> fail) {
;
}
if (node -> son[j] != NULL && node != now) {
node = node -> son[j];
}
next -> fail = node;
q.pb(next);
}
}
}
inline void read() {
char w[LW];
scanf("%s", a);
scanf("%d", &n);
T = new Node;
for (int i = 0; i < n; ++i) {
scanf("%s", w);
ins(T, w, i);
}
bfs();
}
inline void reversedBfs() {
Node* now;
for (int i = int(q.size()) - 1; i > 0; --i) {
now = q[i];
now -> fail -> nr += now -> nr;
for (vector< int >::iterator it = now -> words.begin(), lim = now -> words.end(); it != lim; ++it) {
rez[*it] += now -> nr;
}
}
}
inline void solve() {
int next;
Node *node = T;
for (int i = 0; a[i] != '\0'; ++i) {
next = int(a[i] - 'a');
for (; node != T && node -> son[next] == NULL; node = node -> fail) {
;
}
if (node -> son[next] != NULL) {
node = node -> son[next];
++(node -> nr);
}
}
reversedBfs();
}
inline void print() {
for (int i = 0; i < n; ++i) {
printf("%d\n", rez[i]);
}
}
int main() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
read();
solve();
print();
return 0;
}