Pagini recente » Cod sursa (job #1423267) | Cod sursa (job #1517959) | Cod sursa (job #741911) | Cod sursa (job #820561) | Cod sursa (job #1766122)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100010
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
string A, B;
int N, App[111];
struct Node {
int X;
vector<int> Words;
struct Node *F[26], *Prev;
Node() {
memset(F, 0, sizeof(F));
Prev = 0;
X = 0;
Words.resize(0);
}
};
struct Trie{
Node *R;
vector<Node*> Q;
Trie() {
R = new Node();
Q.resize(0);
}
void Add(string B, int K) {
Node *It = R;
int U;
for (int i = 0; i < B.length(); i++) {
U = B[i]-'a';
if (It->F[U] == NULL) {
It->F[U] = new Node();
}
It = It->F[U];
}
It->Words.push_back(K);
}
void BFS() {
Node *It, *T;
int U;
R->Prev = R;
Q.push_back(R);
for (int i = 0; i < Q.size(); i++) {
It = Q[i];
for (int U = 0; U < 26; U++)
if (It->F[U]) {
for (T = It->Prev; T != R && T->F[U] == 0; T = T->Prev);
if (T->F[U] != 0 && T != It) T = T->F[U];
It->F[U]->Prev = T;
Q.push_back(It->F[U]);
}
}
R->Prev = 0;
}
void Calculate() {
Node *It = R;
int U;
for (int i = 0; i < A.length(); i++) {
U = A[i]-'a';
while (It != R && It->F[U] == 0) It = It->Prev;
if (It->F[U]) {
It = It->F[U];
It->X++;
}
}
}
void Extract() {
Node *It;
for (int i = Q.size() - 1; i >= 0; i--) {
It = Q[i];
for (int j = 0; j < It->Words.size(); j++) {
App[It->Words[j]] = It->X;
}
if (It->Prev) It->Prev->X += It->X;
}
}
} *T;
int main() {
T = new Trie();
f >> A;
f >> N;
for (int i = 1; i <= N; i++) {
f >> B;
T->Add(B, i);
}
T->BFS();
T->Calculate();
T->Extract();
for (int i = 1; i <= N; i++) {
g << App[i] << "\n";
}
return 0;
}