Pagini recente » Cod sursa (job #2028103) | Cod sursa (job #1289583) | Cod sursa (job #2335448) | Cod sursa (job #3189244) | Cod sursa (job #2396947)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int sf[10005],i,j,x,y,a,b,m,n,poz;
string s,s1;
struct trie
{
vector<int> sf;
int np;
trie *cp[26],*f;
trie()
{
//sf=0;
np=0;
f=NULL;
for (int i=0;i<26;i++)
cp[i]=NULL;
}
};
trie *root=new trie;
trie *bfs[1000003];
void ins()
{
int l=s1.size();
trie *nod=root;
for (int j=0;j<l;j++)
{
int ch=s1[j]-'a';
if (nod->cp[ch]==NULL)
nod->cp[ch]=new trie;
nod=nod->cp[ch];
}
nod->sf.push_back(i);
}
int main()
{
fin>>s;
fin>>n;
for (i=1;i<=n;i++)
{
fin>>s1;
ins();
}
root->f=root;
bfs[0]=root;
//queue<trie> q;
int p=1,u=0;
bfs[1]=root;
for (i=0;i<26;i++)
if (root->cp[i]) {root->cp[i]->f=root; bfs[++u]=root->cp[i];}// pe nivelu 1 toate au fail-u in root
else root->cp[i]=root; // pentru cvazu can fail-u tre sa duca in root
while (p<=u)
{
trie *nod=bfs[p];
for (i=0;i<26;i++)
if (nod->cp[i] && nod->cp[i]!=root)
{
trie *fl=nod->f;
while (fl!=root && fl->cp[i]==NULL)
fl=fl->f;
fl=fl->cp[i];
nod->cp[i]->f=fl;
bfs[++u]=nod->cp[i];
//if (nod->cp[i]!=fl)
//for (int j=0;j<fl->sf.size();j++)
// nod->cp[i]->sf.push_back(fl->sf[j]);
}
p++;
}
// fac cu potriviri, tipa invers parcurg, si arat de cate ori so potrivit inca din primu bfs
// si adun numaru de potriviri de la fiecare nod si la fail-u lui,ca tipa e acelasi, si la sfarsit adaug numaru de potrivirai la sfarsit de cuvint, tabelu cu sol
int l=s.size();
trie *nod=root;
for (i=0;i<l;i++)
{
int ch=s[i]-'a';
while (nod!=root && nod->cp[ch]==NULL)
nod=nod->f;
nod=nod->cp[ch];
nod->np++;
//for (int j=0;j<nod->sf.size();j++) sf[nod->sf[j]]++; SCOT!!
}
for (i=u;i>0;i--)
{
if (bfs[i]->f!=root) bfs[i]->f->np+=bfs[i]->np;
for (int j=0;j<bfs[i]->sf.size();j++)
sf[bfs[i]->sf[j]]=bfs[i]->np;
}
for (i=1;i<=n;i++)
fout<<sf[i]<<"\n";
return 0;
}