// http://infoarena.ro/problema/abc2
//
// Folosesc abordarea de aici:
// http://www.infoarena.ro/job_detail/98260?action=view-source
//
// awesome
#include <cstddef>
#include <cstdio>
#include <vector>
namespace abc2
{
size_t const thew = 3; // the w constant
size_t const thew1 = (1+thew);
size_t const maxn = 50000;
size_t const maxc = 20;
size_t const maxc1 = 1+maxc;
size_t const maxc2 = 2+maxc;
size_t const maxv = (maxn*maxc);
size_t const maxv2 = (2+maxv);
size_t const maxm = 10000000;
size_t const maxm1 = (1+maxm);
size_t const maxm2 = (2+maxm);
size_t const HMAX = 666013;
typedef ::std::size_t abcf_node[thew1];
typedef ::std::size_t bft_queue[maxv2];
/// \brief All the data used to solve the problem.
/// The input and extra space used for computing the output.
struct abc2_data
{
/// \brief The trie.
///
/// m_nodes[x][i] == y ↔ (x) --['a'+i]-->(y), i=0..thew-1
/// m_nodes[x][thew] ≠ 0 ↔ x is a leaf in the trie
::std::size_t m_trie[maxv2][thew1];
/// \brief The dfa.
///
/// m_nodes[x][i] == y ↔ (x) --['a'+i]-->(y), i=0..thew-1
/// m_nodes[x][thew] ≠ 0 ↔ x is a final state in the dfa
::std::size_t m_dfa[maxv2][thew1];
/// \brief The queue used in the breadth-first-traversal
/// of states of the dfa.
::std::size_t m_bft[maxv2];
/// \brief Number of occurrences;
::std::size_t m_number_of_occurrences;
/// \brief Space to store all the words in the Makako language
/// , one word after the other, with no separator.
char m_words_symbols[maxv2];
/// The number of words in the Makako language.
::std::size_t m_number_of_words;
/// The length of each word in the Makako language.
::std::size_t m_word_size;
/// \brief Space to store the ancient text.
char m_text_symbols[maxm2];
/// \brief The length of the ancient text.
size_t m_text_size;
// \brief This one is used only in extreme cases.
// Default constructor of ::std::vector should not throw c++ exceptions.
::std::vector<size_t> m_hash_table[HMAX];
} // struct abc2_state
;
// ______________________________________________________________________________
/// \brief Constructs the trie, from the words.
class trie_build_processing
{ private:
abc2_data & m_data;
public:
trie_build_processing
( abc2_data & data
)
throw()
: m_data(data)
{ this->build_trie();
}
private:
void
build_trie
()
throw()
;
} // class trie_build_processing
;
void
trie_build_processing::build_trie
()
throw()
{ // Interation for all words:
::std::size_t s = 0; // The number of nodes in the trie.
::std::size_t i;
abc2_data & d = this->m_data;
abcf_node * trie = d.m_trie;
::std::size_t const z = d.m_number_of_words;
::std::size_t const n = d.m_word_size;
char * p = d.m_words_symbols; // the current word
// Iteration for a word:
::std::size_t x; // position in the trie
::std::size_t j; // position in the current word
::std::size_t c; // current symbol in the current word
::std::size_t y; // next position in the trie
// Iteration for symbols.
::std::size_t t;
for(t=0; thew > t; ++t)
{ trie[s][t] = 0; }
trie[s][thew] = 0; // not a leaf
++s;
for(i=0; z>i; ++i)
{ // Add current word, into the trie.
x = 0;
for(j=0; n>j; ++j)
{ c = p[j]; // c is 0, 1, or 2.
y = trie[x][c];
if(0 == y)
{ for(t=0; thew > t; ++t)
{ trie[s][t] = 0; }
trie[s][thew] = 0; // not a leaf
trie[x][c] = s; y = s; ++s;
}
x = y;
}
trie[x][thew] = 1; // a leaf
// Update position of the current word.
p += n;
}
}
// ______________________________________________________________________________
// ###############################################################################
// ###############################################################################
// ###############################################################################
// Ce proprietăți are automatul finit determinist, cu care vom determina
// pozițiile în T, unde se regăsesc șiruri de simboluri din P?
//
// _______________________________________________________________________________
// Σ este o mulțime finită, oarecare.
// Σ* - șirurilor finite peste Σ.
// ε - șirul fără nici o componentă.
// ε ∈ Σ* . Σ+ = Σ* ∖ {ε}.
//
// P ⊂ Σ+ este o mulțime finită.
// ( P e mulțimea șirurilor pe care le căutăm în șirul T. )
//
// x ∈ Σ+, y ∈ Σ+, i ∈ ℤ, S ⊂ Σ+, S mulțime finită
// λ(x) : lungimea șirului x.
// α(x,i) : prefixul de lungime i, al lui șirului x, atunci când 0 ≤ i ≤ λ(x)
// ω(x,i) : sufixul de lungime i, al șirului x, atunci când 0 ≤ i ≤ λ(x)
// ω(x,0) = ε
// x ⊏ y : ( ( λ(y) > λ(x) ) ∧ ( x = α(y,λ(x)) ) )
// x ⊐ y : ( ( λ(y) > λ(x) ) ∧ ( x = ω(y,λ(x)) ) )
// σ(y) = { x ∈ Σ+ | x ⊐ y }
// π(S) = { x ∈ Σ+ | ∃ y ∈ S (x ⊏ y) }
//
// β(x) = ω(x,max { 0 } ∪ { i ∈ ℤ | 1≤ i ≤ λ(x) ∧ ω(x,i) ∈ π(P) }), ∀ x ∈ Σ+
// _______________________________________________________________________________
//
// Fie D = (Q,Σ,δ,q₀,F) automatul finit construit de acest program.
//
// γ : Σ* → Q, astfel încât γ(ε) = q₀, și ∀ σ ∈ Σ* ∀ c ∈ Σ γ(σc) = δ(γ(σ),c)
// τ : Σ* → ℘(Q), astfel încât τ(ε) = {q₀}, și ∀ σ∈Σ* ∀c∈Σ τ(σc) = τ(σ) ∪ {γ(σc) }
//
// D are următoarele proprietăți:
//
// ▪ q₀ = 0
//
// ▪ ∀ q ∈ Q ( ( q₀ = q ) ∨ ( ∃ x ∈ π(P) ∪ P (q = γ(x)) ) )
//
// ▪ ∀ x ∈ P ( τ(x) = 1 + λ(x) )
//
// ▪ ∀ x ∈ π(P) ∀ c ∈ Σ ( ((xc ∉ π(P) ) ∧ (xc ∉ P)) → (δ(γ(x),c) = γ(β(xc)) ) )
//
// _______________________________________________________________________________
// Care sunt proprietățiile funcției β?
//
// Pentru x ∈ π(P) ∪ P, c ∈ Σ, următoarele sunt proprietăți ale funcției β:
//
// ▪ β(x)c ∈ π(P) → β(xc) = β(x)c
//
// ▪ β(x)c ∉ π(P) → β(xc) = ε
// ###############################################################################
// ###############################################################################
// ###############################################################################
// _______________________________________________________________________________
// The breadth first traversal is needed to compute β, because the breadth
// first traversal explores nodes x, before node y, if the path from the root
// to node x, has fewer edges than the path from the root, to node y.
//
// Consider the example:
// P = { cccccccbaaaaaa
// , aaaaaaaaaaaaaa
// }
// What is the function β, for P.
// β(cccccccbaa) = aa
// It is not possible to derive aa, from cccccccbaa ∈ P alone.
// The value aa is derived from aaaaaaaaaaaaaa ∈ P.
//
// This is what the breadh first traversal does: it prepares values
// needed for computing β, using the recurrence relation.
/// \brief Constructs the dfa, from the trie.
class dfa_build_processing
{ private:
abc2_data & m_data;
public:
dfa_build_processing
( abc2_data & data
)
throw()
: m_data(data)
{ this->build_dfa();
}
private:
void
build_dfa
()
throw()
;
} // class dfa_build_processing
;
void
dfa_build_processing::build_dfa // method
()
throw()
{ abc2_data & d = this->m_data; // data / context
abcf_node * trie = d.m_trie; // the trie
abcf_node * dfa = d.m_dfa; // the dfa
bft_queue & qa = d.m_bft; // queue array
::std::size_t qs = 0; // queue size
::std::size_t qi = 0; // queue index
::std::size_t x; // current state
::std::size_t i; // trie: [ x -- [i] --> y ]
::std::size_t y; // trie: [ x -- [i] --> y ]
::std::size_t t; // x=γ(w), t = γ(β(w·i)), for some w ∈ Σ*
::std::size_t j; // dfa: [ y --[j] --> z ]
::std::size_t z; // dfa: [ y --[j] --> z ]
for(i=0; thew>i; ++i)
{ dfa[0][i] = 0; }
qa[0] = 0; qi = 0; qs = 1;
while(qs > qi) // while
{ x = qa[qi]; ++qi; // Extract state from the bft queue.
dfa[x][thew] = trie[x][thew]; // ≠ 0: final state
for(i=0; thew>i; ++i) // for-1
{ y = trie[x][i];
if(0 != y) // if-1
{ qa[qs] = y; ++qs;
t = dfa[x][i]; // Read t, from dfa[x][i].
dfa[x][i] = y; // Write final value in dfa[x][i].
for(j=0; thew>j; ++j) // for-2
{ z = trie[t][j];
if(0 == z)
{ z = dfa[t][j]; }
dfa[y][j] = z; // "Write t", in dfa[y][j].
} // for-2
} // if-1
} // for-1
} // while
} // method
// ______________________________________________________________________________
/// \brief Solves the abc2 problem, using the DFA.
class solver
{ private:
abc2_data & m_data;
public:
solver
( abc2_data & data
)
: m_data(data)
{ this->process_words();
this->count_number_of_occurrences();
}
private:
void
process_words
()
;
void
count_number_of_occurrences
()
throw()
;
} // class solver
;
void
solver::process_words
()
{ // A two pass algorithm for building the dfa used for
// the multiple pattern matching problem.
abc2_data & d = this->m_data;
// Construct the trie, from words.
trie_build_processing trie_build_processing_object(d);
// The constructor needs to be evaluated on trie_build_processing_object
// because its evaluation contains side effects: it changes the state of
// the m_data object.
(void) trie_build_processing_object;
// Construct the dfa, from trie.
dfa_build_processing dfa_build_processing_object(d);
// Same reasoning about side-effects assures that
// the constructor needs to be evaluated on dfa_build_processing_object.
(void) dfa_build_processing_object;
}
void
solver::count_number_of_occurrences
()
throw()
{ // Count occurrences, using the dfa.
abc2_data & d = m_data;
char * q = d.m_text_symbols;
size_t m = d.m_text_size;
size_t i;
size_t c;
abcf_node * dfa = d.m_dfa;
size_t x = 0;
size_t y;
size_t num = 0; // The number of occurrences.
bool match;
for(i=0 ; m>i; ++i)
{ c = q[i]; // one of 0,1,...,thew-1.
y = dfa[x][c];
match = (0 != (dfa[y][thew]) );
if(match)
{ ++num; }
x = y;
}
// no-throw, no-fail
::std::size_t & ans = d.m_number_of_occurrences;
ans = num;
}
// ______________________________________________________________________________
/// \brief Solves with a hash ( Rabin–Karp algorithm )
namespace yet_another_solver
{
/// \brief Adds words, to hash table.
class words_processing
{ private:
abc2_data & m_data;
public:
words_processing
( abc2_data & data
)
throw()
: m_data(data)
{ build();
}
private:
void
build
()
{ this->initialize_with_no_words();
this->add_words();
}
void
initialize_with_no_words
()
;
void
add_words
()
;
} // class words_processing
;
void
words_processing::initialize_with_no_words
()
{ // Vectors are empty, by default constructor construction.
// Returning, makes solver not re-usable.
return;
abc2_data & d = this->m_data;
::std::vector<size_t> * ht = d.m_hash_table;
size_t i;
for(i=0; HMAX > i; ++i)
{ ht[i].clear(); }
}
void
words_processing::add_words
()
{ // Interation for all words:
size_t i;
abc2_data & d = this->m_data;
size_t const z = d.m_number_of_words;
size_t const n = d.m_word_size;
char * pattern = d.m_words_symbols; // the current word
// Iteration for a word:
size_t j;
size_t sum;
size_t digit;
char symbol;
::std::vector<size_t> * ht = d.m_hash_table;
for(i=0; z>i; ++i)
{ // Add the number for (1+i)-th word, into the set.
sum = 0;
for(j=0; n>j; ++j)
{ symbol = pattern[j];
digit = (static_cast<size_t>(symbol) );
sum = ((3*sum) + digit);
}
ht[sum % HMAX].push_back(sum);
// Update position of the current word.
pattern += n;
}
}
/// \brief Solves the abc2 problem, using the hash table.
class solver
{ private:
abc2_data & m_data;
public:
solver
( abc2_data & data
)
: m_data(data)
{ this->process_words();
this->count_number_of_occurrences();
}
private:
void
process_words
()
;
void
count_number_of_occurrences
()
;
} // class solver
;
void
solver::process_words
()
{ // Construct the finite automaton.
words_processing numbers_for_words_processing(m_data);
// The constructor of numbers_for_words_processing needs
// to be evaluated
// , because its evaluation contains side effects:
// it changes the state of the m_data object
// .
(void) numbers_for_words_processing;
}
void
solver::count_number_of_occurrences
()
{ typedef
::std::vector<size_t>::iterator
ht_iterator
;
// Count occurrences, using the set with numbers for words.
size_t i;
abc2_data & d = m_data;
char * q = d.m_text_symbols;
size_t m = d.m_text_size;
size_t const n = d.m_word_size;
size_t h = 0; // The number of occurrences.
size_t msd = 1; // To remove most significant digit.
size_t sum = 0;
size_t digit;
size_t hc; // hash - code
ht_iterator i0;
ht_iterator i2;
size_t w;
::std::vector<size_t> * ht = d.m_hash_table;
for(i=1; n>i; ++i) { msd = (3*msd); }
for(i=0; ((m>i) && (n>i)); ++i)
{ digit = q[i];
sum = ( (3*sum) + digit);
}
if(n == i)
{ hc = sum % HMAX;
i0 = ht[hc].begin();
i2 = ht[hc].end();
while(i2 != i0)
{ w = ( *i0); ++i0;
if(sum == w)
{ ++h; // match
break;
}
}
}
for( ; m>i; ++i)
{ digit = q[i];
sum = (sum % msd);
sum = ( (3*sum) + digit);
hc = sum % HMAX;
i0 = ht[hc].begin();
i2 = ht[hc].end();
while(i2 != i0)
{ w = ( *i0); ++i0;
if(sum == w)
{ ++h; // match
break;
}
}
}
// no-throw, no-fail
::std::size_t & ans =
d.m_number_of_occurrences;
ans = h;
}
} // namespace yet_another_solver
// ______________________________________________________________________________
/// \brief Reads input.
class input_reader
{ private:
/// \brief The abc2 data.
abc2_data & m_data;
/// \brief Processing is successful.
bool m_ok;
public:
input_reader
( abc2_data & data
, bool & ok
)
: m_data(data)
, m_ok(read_input() )
{ ok = m_ok;
}
private:
bool
read_input
()
throw()
;
} // class input reader.
;
bool
input_reader::read_input
()
throw()
{ freopen("abc2.in", "rt", stdin);
setvbuf(stdin , NULL , _IOFBF , maxm2 + maxv2 + maxn + 1000);
abc2_data & d = this->m_data;
char * q = d.m_text_symbols;
::std::size_t & m = d.m_text_size;
char * p = d.m_words_symbols;
::std::size_t & n = d.m_word_size;
::std::size_t & z = d.m_number_of_words;
::std::size_t i = 0;
char * y = q;
::std::size_t w = 0;
char * s = 0;
fgets(q, maxm2, stdin);
while( ('a' <= (*y))
&& ('c' >= (*y))
)
{ (*y) = (*y) - 'a'; ++y; ++w; }
m = w;
q[m] = '\0';
p[0] = '\0';
y = p; w = 0;
fgets(p, maxc2, stdin);
while( ('a' <= (*y))
&& ('c' >= (*y))
)
{ (*y) = (*y) - 'a'; ++y; ++w; }
n = w;
if( (0 < n) && (1 <= maxn) )
{ i = 1; p += n; p[0] = '\0'; }
s = fgets(p, maxc2, stdin);
while( (0 != s)
&& (i < maxn)
)
{ y = p; w = 0;
while( ('a' <= (*y))
&& ('c' >= (*y))
)
{ (*y) = (*y) - 'a'; ++y; ++w; }
if(n == w)
{ ++i; p += n; p[0] = '\0';
}
s = fgets(p, maxc2, stdin);
}
p[0] = '\0';
z = i;
return true; // Success.
}
// ______________________________________________________________________________
/// \brief Writes output.
class output_writer
{ private:
/// \brief The abc2 data.
abc2_data & m_data;
/// \brief Processing was successful.
bool m_ok;
public:
output_writer
( abc2_data & data
, bool & ok
)
: m_data(data)
, m_ok(write_output() )
{ ok = m_ok;
}
private:
bool
write_output
()
throw()
;
} // class output_writer
;
bool
output_writer::write_output
()
throw()
{ freopen("abc2.out", "wt", stdout);
abc2_data & d = this->m_data;
size_t const & number_of_occurrences =
d.m_number_of_occurrences;
printf("%u\n", number_of_occurrences);
return true; // Success.
}
} // namespace abc2
/// The spaced used by the program.
static
::abc2::abc2_data
s_data;
/// Because the abc2_data is plain old data
/// , the construction of s_data is guaranteed
/// not to throw a c++ exception
/// .
/// True once, fails to be true, with the addition
/// of the ::std::vector<size_t> data member
/// , but no c++ exception is still true.
bool
solve_the_abc2_problem
()
{ ::abc2::abc2_data & d = s_data;
bool ok;
::abc2::input_reader r(d, ok);
if( !ok)
{ return false; } // Failure. No input.
(void) r;
size_t cnst1 = ::abc2::maxc;
bool cond1 = (cnst1>d.m_word_size);
(void) cond1;
(void) cond1;
size_t cnst2 = 3* ( ::abc2::maxv2 / 4);
size_t k1 = d.m_number_of_words;
size_t k2 = d.m_word_size;
k1 = k1 * k2;
bool cond2 = (k1 > cnst2);
if(cond2)
{ // The DFA solution is awesome.
::abc2::solver s(d);
(void) s;
}
else
{ ::abc2::yet_another_solver::solver s(d);
(void) s;
}
::abc2::output_writer w(d, ok);
if( !ok)
{ return false; } // Failure. No output.
return true; // Success.
}
int
main
()
{ int status;
try
{ bool ok = solve_the_abc2_problem();
status = ( ok ? 0 : 1 );
}
catch ( ... )
{ status = 2;
}
return status;
}
Marius B mgnt