Pagini recente » Cod sursa (job #610461) | Cod sursa (job #1140594) | Cod sursa (job #1157323) | Cod sursa (job #2750354) | Cod sursa (job #1232745)
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <deque>
using namespace std;
const char infile[] = "ahocorasick.in";
const char outfile[] = "ahocorasick.out";
ifstream fin(infile);
ofstream fout(outfile);
const int SIGMA = 30;
const int MAXA = 1000005;
const int MAXW = 10005;
const int MAXN = 105;
const int oo = 0x3f3f3f3f;
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; }
struct Trie {
int matches;
Trie *sons[SIGMA], *fail;
vector <int> where;
Trie () {
memset(sons, NULL, sizeof(sons));
matches = 0;
}
};
char A[MAXA], s[MAXW];
int N, p, u, Ans[MAXN];
Trie *Root = new Trie(), *Q[MAXN * MAXW];
void Insert(Trie *Node, const char *s, int where) {
if(!*s) {
Node -> where.push_back(where);
return;
}
int son = *s - 'a';
if(!Node->sons[son])
Node->sons[son] = new Trie();
Insert(Node->sons[son], s + 1, where);
}
inline void BFs() {
Trie *K;
Root->fail = Root;
for(Q[p = u = 1] = Root ; p <= u ; ++ p) {
Trie *Node = Q[p];
for(int son = 0 ; son < SIGMA ; ++ son)
if(Node->sons[son]) {
for(K = Node->fail; K != Root && K -> sons[son] == NULL ; )
K = K->fail;
if(K->sons[son] && K->sons[son] != Node->sons[son]) /// to prevent K for pointing to the same node
K = K->sons[son];
Node->sons[son]->fail = K;
Q[++u] = Node->sons[son];
}
}
}
inline void revBFs() {
for(int i = u ; i ; -- i) {
Trie *Node = Q[i];
if(Node->fail)
Node->fail->matches += Node->matches;
for(vector <int> :: iterator it = Node->where.begin(), fin = Node->where.end(); it != fin ; ++ it)
Ans[*it] = Node->matches;
}
}
int main() {
fin >> (A + 1);
fin >> N;
for(int i = 0 ; i < N ; ++ i) {
fin >> s;
Insert(Root, s, i);
}
BFs();
Trie *K = Root;
int M = strlen(A + 1);
for(int i = 1 ; i <= M ; ++ i) {
int son = A[i] - 'a';
while(K != Root && K -> sons[son] == NULL)
K = K->fail;
if(K->sons[son])
K = K->sons[son];
++ K->matches;
}
revBFs();
for(int i = 0 ; i < N ; ++ i)
fout << Ans[i] << '\n';
fin.close();
fout.close();
return 0;
}