Pagini recente » Cod sursa (job #979380) | Cod sursa (job #2523250) | Cod sursa (job #2729648) | Cod sursa (job #226669) | Cod sursa (job #1170425)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
const int SMAX = 1e6 + 5, WMAX = 1e4 + 5, NMAX = 105;
struct Trie {
Trie *fiu[26], *fail;
int frecv;
vector <int> poz;
Trie() {
for (int i = 0; i < 26; ++i)
fiu[i] = NULL;
fail = NULL;
frecv = 0;
}
} *Root, *Q[WMAX * WMAX];
int st = 1, dr = 1, n, sol[NMAX];
string Input, NOW;
void insertToTrie(string s, int k) {
Trie *Node = Root;
int sz = s.size();
for (int i = 0; i < sz; ++i) {
int Next = s[i] - 'a';
if (Node -> fiu[Next] == NULL)
Node -> fiu[Next] = new Trie;
Node = Node ->fiu[Next];
}
Node -> poz.push_back (k);
}
void bfs() {
Root->fail = Root;
Trie *Node, *Crt;
Q[1] = Root;
while (st <= dr) {
Node = Q[st++];
for (int i = 0; i < 26; ++i)
if (Node -> fiu[i] != NULL) {
for (Crt = Node ->fail; Crt != Root && Crt->fiu[i] == NULL; Crt = Crt -> fail);
if (Crt -> fiu[i] != NULL && Crt -> fiu[i] != Node -> fiu[i])
Crt = Crt -> fiu[i];
Node->fiu[i]->fail = Crt;
Q[++dr] = Node ->fiu[i];
}
}
Root->fail = NULL;
}
void ahoCorasick() {
Trie *Node = Root;
for (int i = 0; i < Input.size(); ++i) {
int Next = Input[i] - 'a';
for (; Node->fiu[Next] == NULL && Node != Root; Node = Node -> fail);
if (Node -> fiu[Next] != NULL)
Node = Node -> fiu[Next];
Node -> frecv++;
}
}
void antiBfs() {
for (int i = dr; i; --i) {
Trie *Node = Q[i];
if (Node -> fail != NULL)
Node -> fail -> frecv += Node -> frecv;
for (vector <int> :: iterator it = Node->poz.begin(); it != Node->poz.end(); ++it)
sol[*it] = Node -> frecv;
}
}
int main() {
Root = new Trie;
fin >> Input >> n;
for (int i = 0; i < n; ++i) {
fin >> NOW;
insertToTrie (NOW, i);// OK
}
bfs(); //OK ?
ahoCorasick(); // OK ?
antiBfs();//OK ?
for (int i = 0; i < n; ++i)
fout << sol[i] << "\n";
}