Pagini recente » Arhiva de probleme | Cod sursa (job #126676) | Cod sursa (job #299193) | Istoria paginii runda/hc_round10/clasament | Cod sursa (job #1244984)
#include<fstream>
#include<iostream>
#include<string.h>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#define NMAX 102
int n;
int sol[NMAX];
string cuv, text;
struct state
{
bool solved;
int father, fail;
int transitions[26];
int grad, sum;
char letter;
vector<int> word;
state(int Father=0, char Letter=0)
{
solved=false;
fail=0;
father=Father;
grad=0;
sum=0;
memset(transitions, 0, sizeof(transitions));
letter=Letter;
}
};
class aho_corasick_automaton
{
public:
vector<state> states;
inline int new_automaton_state(int father=0, char letter=0)
{
states.push_back(state(father, letter));
return states.size()-1;
}
aho_corasick_automaton()
{
new_automaton_state();
}
inline void add_word(const string &s, int cuv_num)
{
int k=0, poz;
for(int i=0; i<s.size(); ++i)
{
poz=s[i]-'a';
if(!states[k].transitions[poz])
{
int x=new_automaton_state(k, s[i]-'a');
states[k].transitions[poz]=x;
}
k=states[k].transitions[poz];
}
states[k].word.push_back(cuv_num);
}
inline void build_fails()
{
queue<int> q;
int nod, k;
q.push(0);
while(!q.empty())
{
nod=q.front();
q.pop();
if(states[nod].father)
{
k=states[states[nod].father].fail;
while(k && !states[k].transitions[states[nod].letter])
k=states[k].fail;
if(states[k].transitions[states[nod].letter])
k=states[k].transitions[states[nod].letter];
states[nod].fail=k;
++states[states[nod].father].grad;
++states[states[nod].fail].grad;
}
states[nod].solved=true;
for(int i=0; i<26; ++i)
if(states[nod].transitions[i] && !states[states[nod].transitions[i]].solved)
q.push(states[nod].transitions[i]);
}
}
void fin()
{
queue<int> q;
int nod;
for(int i=0; i<states.size(); ++i)
if(!states[i].grad)
q.push(i);
while(!q.empty())
{
nod=q.front();
q.pop();
states[states[nod].fail].sum+=states[nod].sum;
--states[states[nod].father].grad;
--states[states[nod].fail].grad;
if(states[nod].father && !states[states[nod].father].grad)
q.push(states[nod].father);
if(states[nod].fail!=states[nod].father && states[nod].father && !states[states[nod].fail].grad)
q.push(states[nod].fail);
}
}
inline int run_automaton(const string &s)
{
int nod=0, aux;
for(int i=0; i<s.size(); ++i)
{
while(nod && !states[nod].transitions[s[i]-'a'])
nod=states[nod].fail;
if(states[nod].transitions[s[i]-'a'])
nod=states[nod].transitions[s[i]-'a'];
++states[nod].sum;
}
}
};
aho_corasick_automaton automaton;
int main()
{
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
ios_base::sync_with_stdio(false);
cin>>text;
cin>>n;
for(int i=1; i<=n; ++i)
{
cin>>cuv;
automaton.add_word(cuv, i);
}
automaton.build_fails();
automaton.run_automaton(text);
automaton.fin();
for(int i=0; i<automaton.states.size(); ++i)
{
for(int j=0;j<automaton.states[i].word.size(); ++j)
sol[automaton.states[i].word[j]]=automaton.states[i].sum;
}
for(int i=1; i<=n; ++i)
cout<<sol[i]<<'\n';
return 0;
}