Pagini recente » Cod sursa (job #977820) | Cod sursa (job #2897945)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
struct Aho_Corasick
{
int indice=0;
int go[26];
int urm[26];
int parinte = -1;
int pch=0;
int link=-1;
int urmdinsir=0;
Aho_Corasick(int Parent =-1,int PCH = -1)
{
parinte = Parent;
pch = PCH;
for (int i=0; i<=26; i++)
{
go[i]=urm[i]=-1;
}
}
};
vector <Aho_Corasick> V(1);
void add_string(string s2,int UndeSunt)
{
int acum = 0;
for (int j=0; j<s2.size(); j++)
{
int loc = s2[j]-'a';
if (V[acum].urm[loc]==-1)
{
V[acum].urm[loc]=V.size();
Aho_Corasick salut = Aho_Corasick(acum,loc);
salut.parinte=acum;
salut.pch=loc;
V.push_back(salut);
}
acum = V[acum].urm[loc];
}
V[acum].indice= UndeSunt;
}
int n,i,sol[105];
string s,s2;
int go(int v,int ch);
int get_link(int v)
{
assert(v!=-1);
if (V[v].link==-1)
{
if (v==0||V[v].parinte==0)
{
V[v].link=0;
}
else
{
V[v].link=go(get_link(V[v].parinte),V[v].pch);
}
}
return V[v].link;
}
int go(int v,int ch)
{
assert(v!=-1);
if (V[v].go[ch]==-1)
{
if (V[v].urm[ch]!=-1)
{
V[v].go[ch]=V[v].urm[ch];
}
else
{
if (v==0)
{
V[v].go[ch]=0;
}
else
{
V[v].go[ch]=go(get_link(v),ch);
}
}
}
return V[v].go[ch];
}
int fr[1000005];
int main()
{
f>>s;
f>>n;
for (i=1; i<=n; i++)
{
f>>s2;
add_string(s2,i);
}
V[0].parinte=0;
for (int j=0; j<V.size(); j++)
{
for (int k=0; k<26; k++)
{
go(j,k);
}
}
queue <int> q;
q.push(0);
while (!q.empty())
{
int acum = q.front();
fr[acum]=0;
q.pop();
int spate= V[acum].link;
auto salut = V[spate];
auto Acum = V[acum];
if (spate!=-1)
{
if (V[spate].indice!=0)
{
V[acum].urmdinsir=spate;
}
else
{
V[acum].urmdinsir = V[spate].urmdinsir;
}
}
for (int j=0; j<26; j++)
{
int Urm = V[acum].urm[j];
if (Urm!=-1)
{
if (fr[Urm]==0)
{
fr[Urm]=1;
q.push(Urm);
}
}
}
}
int acum = 0;
for (int j=0; j<s.size(); j++)
{
acum=go(acum,s[j]-'a');
int copie=acum;
if (V[copie].indice==0)
{
copie = V[copie].urmdinsir;
}
if (copie>0&&V[copie].indice!=0)
{
while (copie>0)
{
sol[V[copie].indice]++;
copie=V[copie].urmdinsir;
}
}
}
for (i=1; i<=n; i++)
{
g<<sol[i]<<'\n';
}
return 0;
}