Pagini recente » Cod sursa (job #1711997) | Cod sursa (job #2763757) | Cod sursa (job #2585377) | Cod sursa (job #589397) | Cod sursa (job #825205)
Cod sursa(job #825205)
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define MAXA 1000050
#define MAXB 10050
#define MAXN 105
char A[MAXA], B[MAXB];
int N, k, nr;
int pi, ps;
int ans[MAXN];
struct ac {
ac *f[26];
ac *fail;
int num;
vector<int> lst;
ac() {
num = 0;
fail = NULL;
for(int i = 0; i < 26; i++)
f[i] = NULL;
}
} *root, *p, *Q[MAXB * MAXB];
void insert(ac *node, char *str, int idx) {
if(!isalpha(*str)) {
node->lst.push_back(idx);
return;
}
int next = *str - 'a';
if(node->f[next] == NULL)
node->f[next] = new ac();
insert(node->f[next], str + 1, idx);
}
void bfs() {
root->fail = root;
Q[1] = root;
for(pi = ps = 1; ps <= pi; ps++) {
ac *fr = Q[ps];
for(int i = 0; i < 26; i++)
if(fr->f[i] != NULL) {
ac *aux = fr->fail;
for(;aux->f[i] == NULL && aux != root; aux = aux->fail);
if(aux->f[i] != NULL && aux->f[i] != fr->f[i])
aux = aux->f[i];
fr->f[i]->fail = aux;
Q[++pi] = fr->f[i];
}
}
root->fail = NULL;
}
void antibfs() {
for(int i = ps - 1; i > 1; i--) {
ac *fr = Q[i];
fr->fail->num += fr->num;
for(vector<int> :: iterator it = fr->lst.begin(); it != fr->lst.end(); it++)
ans[*it] = fr->num;
}
}
int main() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out","w", stdout);
fgets(A, sizeof(A), stdin);
scanf("%d\n", &N);
root = new ac();
for(int i = 0; i < N; i++) {
fgets(B, sizeof(B), stdin);
insert(root, B, i);
}
bfs();
p = root;
for(int i = 0; isalpha(A[i]); i++) {
int next = A[i] - 'a';
while(p->f[next] == NULL && p != root)
p = p->fail;
if(p->f[next] != NULL) {
p = p->f[next];
p->num++;
}
}
antibfs();
for(int i = 0; i < N; i++)
printf("%d\n", ans[i]);
return 0;
}