Pagini recente » Cod sursa (job #2830744) | Cod sursa (job #1985250) | Cod sursa (job #2013396) | Cod sursa (job #2155448) | Cod sursa (job #1236019)
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<string>
using namespace std;
#define NMAX 102
int n;
int sol[NMAX];
string cuv, text;
struct state
{
bool solved;
int father, fail;
int transitions[26];
char letter;
vector<int> word;
state(int Father=0, char Letter=0)
{
solved=false;
fail=0;
father=Father;
memset(transitions, 0, sizeof(transitions));
letter=Letter;
}
};
class aho_corasick_automaton
{
private:
vector<state> states;
inline int new_automaton_state(int father=0, char letter=0)
{
states.push_back(state(father, letter));
return states.size()-1;
}
public:
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(int nod)
{
if(states[nod].father)
{
if(!states[states[nod].father].solved)
build_fails(states[nod].father);
int k=states[states[nod].father].fail;
while(k && !states[k].transitions[states[nod].letter])
{
if(!states[k].fail)
build_fails(k);
k=states[k].fail;
}
if(states[k].transitions[states[nod].letter])
k=states[k].transitions[states[nod].letter];
states[nod].fail=k;
}
states[nod].solved=true;
for(int i=0; i<26; ++i)
if(states[nod].transitions[i] && !states[states[nod].transitions[i]].solved)
build_fails(states[nod].transitions[i]);
}
inline int run_automaton(const string &s)
{
int k=0, aux;
for(int i=0; i<s.size(); ++i)
{
while(k && !states[k].transitions[s[i]-'a'])
k=states[k].fail;
if(states[k].transitions[s[i]-'a'])
k=states[k].transitions[s[i]-'a'];
for(int aux=k; aux; aux=states[aux].fail)
{
for(int j=0; j<states[aux].word.size(); ++j)
++sol[states[aux].word[j]];
}
}
}
};
aho_corasick_automaton automaton;
int main()
{
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
cin>>text;
scanf("%d\n", &n);
for(int i=1; i<=n; ++i)
{
cin>>cuv;
automaton.add_word(cuv, i);
}
automaton.build_fails(0);
automaton.run_automaton(text);
for(int i=1; i<=n; ++i)
printf("%d\n", sol[i]);
return 0;
}