Pagini recente » Cod sursa (job #3276080) | Cod sursa (job #3275240) | Cod sursa (job #657810) | Cod sursa (job #1403185) | Cod sursa (job #1415801)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream F("ahocorasick.in");
ofstream G("ahocorasick.out");
const int N = 1000010;
const int M = 10010;
const int K = 110;
struct aho {
int cnt;
vector<int> words;
aho *sons[26],*fail;
aho()
{
cnt = 0;
fail = NULL;
memset(sons,0,sizeof(sons));
}
} *tree, *p;
int ans[K];
vector<aho*> stk;
void insert(aho *tree,char *str,int index)
{
if ( *str >= 'a' && *str <= 'z' )
{
int where = int(*str) - int('a');
if ( tree->sons[where] == NULL )
{
tree->sons[where] = new aho;
}
insert(tree->sons[where],str+1,index);
}
else
{
tree->words.push_back( index );
return;
}
}
void bfs(aho *tree) /// add fails
// the previous nodes are already built , so run something similar to KMP
{
queue< aho* > q;
tree->fail = tree;
q.push(tree);
while ( !q.empty() )
{
aho *now = q.front();
q.pop();
for (int i=0;i<26;++i)
if ( now->sons[i] != NULL )
{
aho* aux = now->fail;
while ( aux != tree && aux->sons[i] == NULL )
// if I haven't reached the root and the requested son doesn't exist
// go backwards ( like in pi function at KMP )
aux = aux->fail;
if ( aux->sons[i] != NULL && aux->sons[i] != now->sons[i] )
// normally go to the son , but there are cases where the fail remains a
// backward edge
aux = aux->sons[i];
now->sons[i]->fail = aux;
q.push( now->sons[i] );
stk.push_back( now->sons[i] );
}
}
tree->fail = NULL;
}
void reverse_bfs() // computes the solution
// add the cnt from the node to the bigest common suffix
{
for (;!stk.empty();stk.pop_back())
{
aho *now = stk.back();
if ( now->fail != NULL )
now->fail->cnt += now->cnt;
for (int j=0;j<int(now->words.size());++j)
ans[ now->words[j] ] = now->cnt;
}
}
char text[N],word[N];
int n;
int main()
{
F>>text;
F>>n;
tree = new aho;
for (int i=1;i<=n;++i)
{
F>>word;
insert(tree,word,i);
}
bfs(tree);
p = tree; // p is the pointer that travels inside the automaton
int ln = strlen(text);
for (int i=0;i<ln;++i)
{
int where = int(text[i]) - int('a');
while ( p->sons[where] == NULL && p != tree )
p = p->fail;
if ( p->sons[where] != NULL )
p = p->sons[where];
++p->cnt;
}
reverse_bfs();
for (int i=1;i<=n;++i)
G<<ans[i]<<'\n';
}