Pagini recente » Cod sursa (job #2088948) | Cod sursa (job #1444993) | Cod sursa (job #1279359) | Atasamentele paginii vacanta_11_3 | Cod sursa (job #3204144)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
typedef long long ll;
string a;
string dex[105];
int n,i;
vector <int> nodterm;
struct varf
{
int next[26],tran[26];
int link,tata,lit;
bool terminal=false;
varf()
{
for(int i=0;i<26;i++)
next[i]=tran[i]=-1;
tata=lit=link=-1;
}
};
vector <varf> trie(1);
void addstring(string s)
{
int nod=0;
varf nou;
for(auto ch:s)
{
int c=ch-'a';
if(trie[nod].next[c]==-1)
{
nou.tata=nod;
nou.lit=c;
trie[nod].next[c]=trie.size();
trie.push_back(nou);
}
nod=trie[nod].next[c];
}
trie[trie.size()-1].terminal=true;
nodterm.push_back(nod);
}
int pi(int);
int sigma(int,int);
int dp[1000005];
ll ans=0;
void aho_corasick(string s)
{
for(int i=0;i<trie.size();i++)
{
pi(i);
for(int j=0;j<26;j++)
sigma(i,j);
}
int nod=0;
for(int i=0;i<=s.size();i++)
{
nod=trie[nod].tran[s[i]-'a'];
dp[nod]++;
}
vector <int> parcurgere;
parcurgere.push_back(0);
for(int i=0;i<parcurgere.size();i++)
{
int nod=parcurgere[i];
for(int j=0;j<26;j++)
if(trie[nod].next[j]!=-1)
parcurgere.push_back(trie[nod].next[j]);
}
reverse(parcurgere.begin(),parcurgere.end());
for(int i:parcurgere)
{
dp[trie[i].link]+=dp[i];
}
for(int i:nodterm)
fout<<dp[i]<<'\n';
}
int main()
{
fin>>a;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>dex[i];
addstring(dex[i]);
}
aho_corasick(a);
return 0;
}
int pi(int nod)
{
if(trie[nod].link==-1)
{
if(!nod||!trie[nod].tata)
trie[nod].link=0;
else
trie[nod].link=sigma(pi(trie[nod].tata),trie[nod].lit);
}
return trie[nod].link;
}
int sigma(int nod,int lit)
{
if(trie[nod].tran[lit]==-1)
{
if(trie[nod].next[lit]!=-1)
trie[nod].tran[lit]=trie[nod].next[lit];
else
if(nod!=0)
trie[nod].tran[lit]=sigma(pi(nod),lit);
else
trie[nod].tran[lit]=0;
}
return trie[nod].tran[lit];
}