Pagini recente » Cod sursa (job #532987) | Cod sursa (job #823512)
Cod sursa(job #823512)
#include<cstdio>
#include<queue>
using namespace std;
struct node
{bool final;
int appereances;
node *pref,*link[26],*nextDictWord;
vector<int> wordnr;
node()
{memset(this,0,sizeof(node)),memset(link,0,26),
final=appereances=0,nextDictWord=NULL;}};
node *root=new node(),*currentnode;
int i,n,b[101],j;
char s[1000001],a[10001];
vector<node*> ordbf;
node *linknode(node *r,char x)
{if(!r->link[x-'a'])
r->link[x-'a']=new node();
return r->link[x-'a'];}
void setfinal(node *r,int x)
{r->final=true,r->wordnr.push_back(x);}
void add(char *s,int wordnr)
{node *currentnode=root;
root->final=true;
for(int i=0;s[i];i++)
currentnode=linknode(currentnode,s[i]);
setfinal(currentnode,wordnr);}
void ac(node *root)
{int i;
queue<node*> coada;
for(i=0;i<26;i++)
if(root->link[i])
coada.push(root->link[i]),ordbf.push_back(root->link[i]),root->link[i]->pref=root;
node *tata,*fiu,*aux;
while(!coada.empty())
{tata=coada.front(),coada.pop();
for(i=0;i<26;i++)
if(tata->link[i])
{fiu=tata->link[i],aux=tata->pref;
coada.push(fiu),ordbf.push_back(fiu);
for(aux=tata->pref;aux&&!aux->link[i];aux=aux->pref);
fiu->pref=aux->link[i];
if(!aux)
fiu->pref=root;
for(aux=fiu->pref;aux&&!aux->final;aux=aux->pref);
fiu->nextDictWord=aux;}}}
int main()
{freopen("ahocorasick.in","r",stdin),freopen("ahocorasick.out","w",stdout);
gets(s),scanf("%d\n",&n);
for(j=1;j<=n;j++)
gets(a),add(a,j);
ac(root),currentnode=root;
for(i=0;s[i];i++)
{while(!currentnode->link[s[i]-'a']&¤tnode!=root)
currentnode=currentnode->pref;
if(currentnode->link[s[i]-'a'])
currentnode=currentnode->link[s[i]-'a'],currentnode->appereances++;}
for(i=0;i<ordbf.size();i++)
if(ordbf[i]->final)
{if(ordbf[i]->nextDictWord!=root&&ordbf[i]->nextDictWord)
ordbf[i]->nextDictWord->appereances+=ordbf[i]->appereances;
for(j=0;j<ordbf[i]->wordnr.size();j++)
b[ordbf[i]->wordnr[j]]=ordbf[i]->appereances;}
for(i=1;i<=n;i++)
printf("%d\n",b[i]);
return 0;}