Pagini recente » Cod sursa (job #117518) | Cod sursa (job #721133) | abcdefghijklmnopqrstuvwxyz | Cod sursa (job #3122495) | Cod sursa (job #3204014)
#include <fstream>
#include <vector>
const int NMAX=1e6+5;
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct node
{
int next[26], tran[26];
int fath, ch, link;
node()
{
int i;
for(i=0; i<26; i++)
next[i]=tran[i]=-1;
link=-1; fath=ch=-1;
}
};
vector <node> trie;
vector <int> st, fans;
int dp[NMAX]; ///nr de terminatii ale cuvintelor
char s[NMAX], t[NMAX];
void trie_insert(char *);
void build_aho_corasick();
int pi(int); ///sufflink aka muchii cu epsilon
int sigma(int, int); ///tran aka iti duce la capatul celor cu epsilon
void pls_solve(char *);
int main()
{
int i, n;
fin>>s;
node root;
trie.push_back(root);
fin>>n;
for(i=0; i<n; i++)
{
fin>>t;
trie_insert(t);
}
build_aho_corasick();
pls_solve(s);
for(i=0; i<n; i++) fout<<dp[fans[i]]<<'\n';
return 0;
}
void trie_insert(char *s)
{
node new_node;
int node=0, i;
for(i=0; s[i]; i++)
{
if(trie[node].next[s[i]-'a']==-1)
{
new_node.fath=node;
new_node.ch=s[i]-'a';
trie.push_back(new_node);
trie[node].next[s[i]-'a']=trie.size()-1;
}
node=trie[node].next[s[i]-'a'];
}
fans.push_back(node);
}
void build_aho_corasick()
{
int i, j;
for(i=0; i<int(trie.size()); i++)
{
pi(i);
for(j=0; j<26; j++) sigma(i, j);
}
}
int pi(int node)
{
if(trie[node].link==-1)
{
if(!node || !trie[node].fath)
trie[node].link=0;
else trie[node].link=sigma(pi(trie[node].fath), trie[node].ch);
}
return trie[node].link;
}
int sigma(int node, int ch)
{
if(trie[node].tran[ch]==-1)
{
if(trie[node].next[ch]!=-1)
trie[node].tran[ch]=trie[node].next[ch];
else if(node) trie[node].tran[ch]=sigma(pi(node), ch);
else trie[node].tran[ch]=0;
}
return trie[node].tran[ch];
}
void pls_solve(char *s)
{
int node=0, i, j;
for(i=0; s[i]; i++)
{
node=trie[node].tran[s[i]-'a'];
dp[node]++;
}
st.push_back(0);
for(i=0; i<int(st.size()); i++)
{
node=st[i];
for(j=0; j<26; j++)
{
if(trie[node].next[j]!=-1)
st.push_back(trie[node].next[j]);
}
}
for(i=int(st.size())-1; i>=0; i--)
{
node=st[i];
dp[trie[node].link]+=dp[node];
}
}