Pagini recente » Cod sursa (job #2130155) | Cod sursa (job #845289) | Cod sursa (job #2282966) | Cod sursa (job #664086) | Cod sursa (job #1468234)
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int NMAX = 1000005;
const int MMAX = 10005;
int N;
char A[NMAX], cuv[MMAX];
class Trie
{
public:
Trie * fii[26];
Trie * fail;
int val;
vector<Trie*> V;
Trie() : fail(0), val(0) { memset(fii, 0, sizeof(fii)); }
};
Trie * Root = new Trie();
Trie * cuvinte[105];
queue<Trie*> Q;
void add(Trie * nod, char cuv[], int index)
{
if(*cuv == 0) {
cuvinte[index] = nod;
return;
}
if(nod -> fii[*cuv - 'a'] == 0)
nod -> fii[*cuv - 'a'] = new Trie();
add(nod -> fii[*cuv - 'a'], cuv + 1, index);
}
void dfs(Trie * nod)
{
for(auto x : nod -> V) {
dfs(x);
nod -> val += x -> val;
}
}
int main()
{
fin >> A >> N;
for(int i=1; i<=N; i++) {
fin >> cuv;
add(Root, cuv, i);
}
Q.push(Root);
while(!Q.empty())
{
Trie * C = Q.front(); // C = current trie
Q.pop();
for(int i=0; i<26; i++) {
if(C -> fii[i]) {
Trie * nod = C -> fail;
while(nod && nod -> fii[i] == 0)
nod = nod -> fail;
if(!nod) {
C -> fii[i] -> fail = Root;
Root -> V.push_back(C -> fii[i]);
}
else {
C -> fii[i] -> fail = nod -> fii[i];
nod -> fii[i] -> V.push_back(C -> fii[i]);
}
Q.push(C -> fii[i]);
}
}
}
Trie * C = Root;
for(int i=0; A[i]; i++) {
while(C && C -> fii[A[i] - 'a'] == 0)
C = C -> fail;
if(!C) C = Root;
else C = C -> fii[A[i] - 'a'];
(C -> val)++;
}
dfs(Root);
for(int i=1; i<=N; i++)
fout << cuvinte[i] -> val << '\n';
return 0;
}