Pagini recente » Cod sursa (job #2204457) | Cod sursa (job #289523) | Cod sursa (job #1814579) | Clasament testroundid | Cod sursa (job #1074308)
#include <fstream>
#include <list>
#include <bitset>
#include <string.h>
using namespace std;
const char infile[] = "ahocorasick.in";
const char outfile[] = "ahocorasick.out";
ifstream fin(infile);
ofstream fout(outfile);
const int MAXL = 1000005;
const int oo = 0x3f3f3f3f;
const int MAXN = 105;
const int MAXS = 10005;
const int SIGMA = 26;
const char DELTA = 'a';
const inline int min(const int &a, const int &b) { if( a > b ) return b; return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b; return a; }
const inline void Get_min(int &a, const int b) { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b) { if( a < b ) a = b; }
int N, p, u, Ans[MAXN];
char A[MAXL], S[MAXS];
struct Trie {
int matches;
Trie *sons[SIGMA], *fail;
list <int> where; /// TODO: implement the arrays as a linked list
Trie() { /// constructor
where.clear(); /// not needed
memset(sons, 0, sizeof(sons));
fail = 0;
matches = 0;
}
};
Trie *Root = new Trie(), *P, *Q[MAXN * MAXS];
void Insert(Trie * Node, const char *p, const int &ind) {
if(!*p) {
Node -> where.push_back(ind);
return;
}
int son = *p - DELTA;
if(!Node -> sons[son])
Node -> sons[son] = new Trie();
Insert(Node -> sons[son], p + 1, ind);
}
inline void BFs(Trie* stNode) {
Trie *tmp;
stNode -> fail = stNode;
for(Q[p = u = 1] = stNode ; p <= u ; ++ p) {
Trie *Node = Q[p];
for(int i = 0 ; i < SIGMA ; ++ i)
if(Node -> sons[i]) {
for(tmp = Node -> fail ; tmp != stNode && !(tmp -> sons[i]) ; tmp = tmp -> fail);
if(tmp -> sons[i] && tmp -> sons[i] != Node -> sons[i])
tmp = tmp -> sons[i];
Node -> sons[i] -> fail = tmp;
Q[ ++ u ] = Node -> sons[i];
}
}
stNode -> fail = 0;
}
inline void revBFs(const Trie* stNode) {
for(int i = u ; i ; -- i) {
Trie *Node = Q[i];
if(Node -> fail)
Node -> fail -> matches += Node -> matches;
for(list <int> :: iterator it = Node -> where.begin(), fin = Node -> where.end(); it != fin ; ++ it)
Ans[*it] = Node -> matches;
}
}
int main() {
fin.getline(A, MAXL);
int L = strlen(A);
fin >> N;
fin.get();
for(int i = 0 ; i < N ; ++ i) {
fin.getline(S, MAXS);
Insert(Root, S, i);
}
BFs(Root);
P = Root;
for(int i = 0 ; i < L ; ++ i) {
int son = A[i] - DELTA;
for( ; (!P -> sons[son]) && P != Root ; P = P -> fail);
if(P -> sons[son])
P = P -> sons[son];
++ P -> matches;
}
revBFs(Root);
for(int i = 0 ; i < N ; ++ i)
fout << Ans[i] << '\n';
fin.close();
fout.close();
return 0;
}