Pagini recente » Cod sursa (job #964430) | Cod sursa (job #646849) | Cod sursa (job #2299573) | Cod sursa (job #1201226) | Cod sursa (job #988021)
Cod sursa(job #988021)
#include <fstream>
#include <string.h>
#include <vector>
#define maxwordlen 10001
#define maxtextlen 1000001
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct trie_node
{
vector <short> which;
int nr;
trie_node *s[26],*fail;
trie_node ()
{
nr=0;
for (int i=0; i<26; ++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.push_back(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<26; ++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;
for (int j=0; j<q[i]->which.size(); ++j) v[q[i]->which[j]] = 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";
}