Pagini recente » Cod sursa (job #2164270) | Cod sursa (job #323558) | Cod sursa (job #1046466) | Cod sursa (job #3234941) | Cod sursa (job #2921478)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
string s;
int ap[101];
struct Trie{
bool exis;
vector <int> care;
Trie *fiu[26],*tata;
Trie *fail;
Trie *green;
Trie(Trie *daddy){
for(int i=0;i<26;i++)
fiu[i]=NULL;
fail=NULL;
tata=daddy;
exis=0;
}
};
queue <Trie*> coada;
Trie *root=new Trie(NULL);
void baga(Trie *nod,char a[],int poz)
{
if(a[0]==0)
{
nod->care.push_back(poz);
nod->exis=1;
return;
}
if(nod->fiu[a[0]-'a']==NULL)
{
Trie *urm=new Trie(nod);
nod->fiu[a[0]-'a']=urm;
}
baga(nod->fiu[a[0]-'a'],a+1,poz);
}
char a[10001];
int main()
{
int i,q;
in>>s;
in>>q;
for(i=1;i<=q;i++)
{
in>>a;
//out<<(int)a[strlen(a)]<<'\n';
baga(root,a,i);
}
for(i=0;i<26;i++)
if(root->fiu[i]==NULL)
root->fiu[i]=root;
else
{
coada.push(root->fiu[i]);
root->fiu[i]->fail=root;
root->fiu[i]->green=root;
}
while(coada.size())
{
Trie *cur=coada.front();
coada.pop();
for(i=0;i<26;i++)
if(cur->fiu[i]!=NULL)
{
coada.push(cur->fiu[i]);
Trie *inc=cur->fail;
while(inc->fiu[i]==NULL)
inc=inc->fail;
cur->fiu[i]->fail=inc->fiu[i];
if(inc->fiu[i]->exis)
cur->fiu[i]->green=inc->fiu[i];
else
cur->fiu[i]->green=inc->fiu[i]->green;
if(cur->fiu[i]->exis)
for(auto it:cur->fiu[i]->green->care)
cur->fiu[i]->care.push_back(it);
}
}
Trie *start=root;
root->green=root;
for(i=0;i<s.size();i++)
{
while(start->fiu[s[i]-'a']==NULL)
start=start->fail;
start=start->fiu[s[i]-'a'];
Trie *interes=start;
if(!interes->exis)
interes=interes->green;
for(auto it:interes->care)
ap[it]++;
}
for(i=1;i<=q;i++)
out<<ap[i]<<'\n';
return 0;
}