Pagini recente » Cod sursa (job #480917) | Cod sursa (job #1886805) | Cod sursa (job #2465654) | Cod sursa (job #3280561) | Cod sursa (job #1251487)
#include<fstream>
#include<cstring>
#include<vector>
#define N 100100
#define M 10010
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
int i,n,j,sol[N];
char s[N],s1[M];
struct aho{
vector<int>v;
aho *fii[26],*fail;
int nr;
aho(){
fail = NULL;
nr = 0;
memset(fii, NULL, sizeof(fii));
}
};
aho *t,*nod,*nod2;
vector<aho*>q;
inline void insert(char *p, int poz){
nod = t;
while(*p)
{
if(!nod -> fii[*p - 'a'])
nod -> fii[*p - 'a'] = new aho;
nod = nod -> fii[*p - 'a'];
++p;
}
nod -> v.push_back(poz);
}
inline void Bfs(){
t -> fail = t;
q.push_back(t);
for(i = 0; i < q.size(); ++i)
{
nod = q[i];
for(j = 0; j <= 25; ++j)
if(nod -> fii[j])
{
nod2 = nod -> fail;
while(nod2 != t && !nod2 -> fii[j])
nod2 = nod2 -> fail;
if(nod2 -> fii[j] && nod2 -> fii[j] != nod -> fii[j])
nod2 = nod2 -> fii[j];
nod -> fii[j] -> fail = nod2;
q.push_back(nod -> fii[j]);
}
}
t -> fail = NULL;
}
inline void AntiBfs(){
for(i = q.size() - 1; i; --i)
{
nod = q[i];
nod -> fail -> nr += nod -> nr;
for(vector<int>::iterator it = nod -> v.begin(); it != nod -> v.end(); ++it)
sol[*it] = nod -> nr;
}
}
int main()
{
t = new aho;
f >> (s + 1) >> n;
for(i = 1; i <= n; ++i)
{
f >> s1;
insert(s1, i);
}
Bfs();
nod = t;
for(i = 1; s[i]; ++i)
{
while(nod != t && !nod -> fii[s[i] - 'a'])
nod = nod -> fail;
if(nod -> fii[s[i] - 'a'])
nod = nod -> fii[s[i] - 'a'];
++nod -> nr;
}
AntiBfs();
for(i = 1; i <= n; ++i)
g << sol[i] << '\n';
return 0;
}