Pagini recente » Cod sursa (job #2968565) | Cod sursa (job #29506) | Cod sursa (job #2199642) | Cod sursa (job #2908226) | Cod sursa (job #988013)
Cod sursa(job #988013)
#include <fstream>
#include <string.h>
#define maxwordlen 10001
#define maxtextlen 1000001
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct trie_node
{
short which;
int nr;
trie_node *s[25],*fail;
trie_node ()
{
which=0;
nr=0;
for (int i=0; i<25; ++i) s[i]=NULL;
fail=NULL;
}
}*trie,*q[100*maxwordlen];
char word[maxwordlen],text[maxtextlen];
int v[101],wordlen,textlen,i,s,l,n;
void trie_insert (trie_node *current, int j)
{
if (j==wordlen) {current->which=i; return;}
int letter = word[j] - 'a';
if (current->s[letter]==NULL) current->s[letter] = new trie_node;
trie_insert (current->s[letter],j+1);
}
void bfs ()
{
s=1,l=1;
q[l] = trie;
trie->fail = trie;
while (s <= l)
{
for (int i=0; i<25; ++i)
if (q[s]->s[i] != NULL)
{
trie_node *back=q[s]->fail;
while (back!=trie && back->s[i]==NULL) back = back->fail;
if (back->s[i]!=NULL && back!=q[s]) back = back->s[i];
q[s]->s[i]->fail=back;
q[++l] = q[s]->s[i];
}
++s;
}
}
void antibfs ()
{
for (int i=l; i>=1; --i)
{
q[i]->fail->nr += q[i]->nr;
v[q[i]->which] = q[i]->nr;
}
}
int main()
{
trie = new trie_node;
fin>>text;
fin>>n;
for (i=1; i<=n; ++i)
{
fin>>word;
wordlen = strlen (word);
trie_insert (trie,0);
}
bfs ();
textlen = strlen (text);
trie_node *current = trie;
for (int i=0; i<textlen; ++i)
{
int letter = text[i]-'a';
while (current->s[letter]==NULL && current!=trie) current = current->fail;
if (current->s[letter]!=NULL)
{
current = current->s[letter];
current->nr++;
}
}
antibfs();
for (int i=1; i<=n; ++i) fout<<v[i]<<"\n";
}