// http://infoarena.ro/problema/abc2
//
// Folosesc abordarea de aici:
// http://www.infoarena.ro/job_detail/98260?action=view-source
//
// Construiesc un trie.
// Schimb trie-ul, într-un dfa.
// Identific pozițiile candidat, cu dfa-ul.
//
// Timpul pentru construirea trie-ului: O(z·n)
// Timpul pentru schimbarea trie-ului, în dfa: O(z·n·w)
// Timpul pentru identificarea pozițiiloe candidat, cu dfa-ul: O(m).
// z - numărul cuvintelor, z ≤ 50 000
// n - lungimea fiecărui cuvânt, n ≤ 20
// w - cardinalul mulțimii literelor folosite de cuvinte, w = 3
// m - numărul literelor din textul antic, m ≤ 10 000 000
// .
//
// O(max(m,z·n·w, z·n)
// .
// http://www.infoarena.ro/job_detail/98260?action=view-source
// awesome
#include <cstddef>
#include <stdexcept>
#include <string>
#include <iostream>
#include <fstream>
#include <set>
// cstring declares ::std::strlen
#include <cstring>
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 maxc2 = 2+maxc;
size_t const maxv = (maxn*maxc);
size_t const maxv2 = (2+maxv);
size_t const maxm = 10000000;
size_t const maxm2 = (2+maxm);
typedef ::std::size_t abcf_node[thew1];
typedef ::std::size_t bft_queue[maxv2];
typedef int unsigned uint32; // may be more than 32
/// \brief All the data used to solve the problem.
/// The input and extra space used for computing the output.
struct abc2_data
{ /// \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 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 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;
} // 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.
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 Shifts input from 'a', 'b', 'c', to '\0x0', '\0x1', '\0x2'
class input_translation
{ private:
/// \brief The abc2 data.
abc2_data & m_data;
/// \brief Processing was successful (data was valid).
bool m_ok;
public:
input_translation
( abc2_data & data
, bool & ok
)
throw()
;
private:
bool
shift_input
()
throw()
;
static
bool
shift_sz // sz- string zero; in-place
( char * sz
)
throw
()
;
} // class input_translation
;
input_translation::input_translation
( abc2_data & data
, bool & ok
)
throw()
: m_data(data)
, m_ok(this->shift_input() )
{ ok = m_ok;
}
bool
input_translation::shift_input
()
throw()
{ bool ok;
abc2_data & d = this->m_data;
char * q = d.m_text_symbols;
char * p = d.m_words_symbols;
ok = this->shift_sz(q);
if( !ok)
{ return false; } // Failure.
ok = this->shift_sz(p);
if( !ok)
{ return false; } // Failure.
return true; // Success.
}
bool
input_translation::shift_sz
( char * p
)
throw()
{ bool ok;
char c = ( *p);
while('\0' != c)
{ ok = (('a' <= c) && ('c' >= c));
if( !ok)
{ return false; } // Failure.
c = c - 'a'; (*p) = c; ++p; c = ( *p);
}
return true; // Success.
}
// ______________________________________________________________________________
/// \brief Verifies if the string is an abc string.
class string_is_an_abc_string
{ private:
/// \brief The string.
char * m_p;
/// \brief The length of the string.
size_t m_k;
/// \brief Is an abc string.
bool m_is_an_abc_string;
public:
string_is_an_abc_string
( char * p
, size_t k
)
: m_p(p)
, m_k(k)
, m_is_an_abc_string(is_an_abc_string() )
{}
private:
bool
is_an_abc_string
()
const
throw()
;
public:
operator
bool
()
throw()
{ return m_is_an_abc_string; }
} // class string_is_an_abc_string
;
bool
string_is_an_abc_string::is_an_abc_string
()
const
throw()
{ char * p = m_p;
size_t k = m_k;
size_t i;
char c;
bool ok;
for(i=0; k>i; ++i)
{ c = p[i];
ok = ( ('a' == c)
|| ('b' == c)
|| ('c' == c)
)
;
if( !ok)
{ return false; } // It is not an abc string.
}
return true; // It is an abc string.
}
// ______________________________________________________________________________
/// \brief Reads the Makoko language.
class makako_language_reader
{ private:
/// \brief Reference to the input stream.
::std::istream & m_is;
/// \brief Reference to the abc2 data.
abc2_data & m_data;
/// \brief Reference to the input is not valid variable.
bool & m_input_is_not_valid;
/// \brief Reference to the io-error-occurred variable.
bool & m_io_error_occurred;
/// \brief Processing was successful.
bool m_ok;
public:
makako_language_reader
( ::std::istream & is
, abc2_data & data
, bool & input_is_not_valid
, bool & io_error_occurred
, bool & ok
)
throw()
;
private:
bool
read_the_makako_language
()
throw()
;
bool
read_word
( char * p
, size_t & k
)
throw()
;
bool
read_the_last_line
()
throw()
;
} // class makako_language_reader
;
makako_language_reader::makako_language_reader
( ::std::istream & is
, abc2_data & data
, bool & input_is_not_valid
, bool & io_error_occurred
, bool & ok
)
throw()
: m_is(is)
, m_data(data)
, m_input_is_not_valid(input_is_not_valid)
, m_io_error_occurred(io_error_occurred)
, m_ok(read_the_makako_language() )
{ ok = m_ok;
}
bool
makako_language_reader::read_the_makako_language
()
throw()
{ bool ok;
abc2_data & d = this->m_data;
char * p = d.m_words_symbols;
size_t len;
// Read first word.
ok = this->read_word(p, len);
if( !ok)
{ return false; } // Failure.
bool const first_is_empty = (0>=len);
// Read remaining words.
size_t const len0 = len;
size_t i = 1;
while((maxn > i) && (0<len))
{ p += len0;
ok = this->read_word(p, len);
if( !ok)
{ return false; } // Failure.
ok = ((len0 == len) || (0 == len));
if( !ok)
{ return false; }
++i;
}
// Read last line.
if(0 != len)
{ ok = read_the_last_line();
if( !ok)
{ return false; } // Failure.
}
else
{ if(false == first_is_empty)
{ --i; }
}
// no-throw, no-fail
::std::size_t & number_of_words =
d.m_number_of_words;
::std::size_t & word_size =
d.m_word_size;
number_of_words = i;
word_size = len0;
return true; // Success.
}
bool
makako_language_reader::read_word
( char * p
, size_t & k
)
throw()
{ ::std::istream & is = this->m_is;
bool ok;
bool withSeparator = true;
is.getline(p, maxc2);
ok = is.good();
if( !ok)
{ ok = is.eof();
if( !ok)
{ m_io_error_occurred = true;
return false; // Failure.
}
withSeparator = false;
}
// Compute len, line lenth.
::std::streamsize tmp = is.gcount();
if(0 > tmp)
{ m_io_error_occurred = true;
return false; // Failure.
}
if(0 < tmp)
{ if(withSeparator)
{ --tmp; }
}
size_t len = static_cast<size_t>(tmp);
p[len] = '\0'; // Only for "(gdb) print p".
ok = (len<=maxc);
if( !ok)
{ m_input_is_not_valid = true;
return false; // Failure.
}
ok = string_is_an_abc_string(p, len);
if( !ok)
{ m_input_is_not_valid = true;
return false; // Failure.
}
// no-throw, no-fail
k = len;
return true; // Success.
}
bool
makako_language_reader::read_the_last_line
()
throw()
{ ::std::istream & is = m_is;
bool ok;
bool withSeparator = true;
// Read line, into variable space.
char space[2];
is.getline(space, 2);
ok = is.good();
if( !ok)
{ ok = is.eof();
if( !ok)
{ m_io_error_occurred = true;
return false; // Failure.
}
withSeparator = false;
}
// Compute line length, into variable len.
::std::streamsize tmp = is.gcount();
if(0 > tmp)
{ m_io_error_occurred = true;
return false; // Failure.
}
if(0 < tmp)
{ if(withSeparator)
{ --tmp; }
}
::std::size_t len = static_cast< ::std::size_t>(tmp);
space[len] = '\0'; // Only for "(gdb) print space".
ok = (0 == len);
if( !ok)
{ m_input_is_not_valid = true;
return true; // Failure.
}
return true; // Success.
}
// ______________________________________________________________________________
/// \brief Reads the input.
class input_reader
{ private:
/// \brief The abc2 data.
abc2_data & m_data;
/// \brief Input is not valid.
///
/// This data member is initialized
/// , only when processing is not successful.
bool m_input_is_not_valid;
/// \brief Input error occurred.
///
/// This data member is initialized
/// , only when processing is not successful.
bool m_io_error_occurred;
/// \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()
;
bool
read_the_ancient_text
( ::std::istream & is
)
throw()
;
bool
read_all_the_words_in_the_makako_language
( ::std::istream & is
)
throw()
;
} // class input reader.
;
bool
input_reader::read_input
()
throw()
{ bool ok;
::std::ifstream is("abc2.in");
ok = is.good();
if( !ok)
{ m_io_error_occurred = true;
return false;
}
ok = this->read_the_ancient_text(is);
if( !ok)
{ return false; } // Failure.
ok = this->read_all_the_words_in_the_makako_language(is);
if( !ok)
{ return false; } // Failure.
return true; // Success.
}
bool
input_reader::read_the_ancient_text
( ::std::istream & is
)
throw()
{ abc2_data & d = this->m_data;
char * p = d.m_text_symbols;
// Read line.
bool withSeparator = true;
is.getline(p, maxm2);
bool ok = is.good();
if( !ok)
{ ok = is.eof();
if( !ok)
{ m_io_error_occurred = true;
return false; // Failure.
}
withSeparator = false;
}
// Compute line length.
::std::streamsize tmp = is.gcount();
if(0 > tmp)
{ m_io_error_occurred = true;
return false; // Failure.
}
if(0 < tmp)
{ if(withSeparator)
{ --tmp; }
}
::std::size_t len =
static_cast< ::std::size_t>(tmp);
p[len] = '\0';
ok = (len <= maxm);
if( !ok)
{ m_input_is_not_valid = true;
return false; // Failure.
}
ok = string_is_an_abc_string(p, len);
if( !ok)
{ m_input_is_not_valid = true;
return false; // Failure.
}
::std::size_t & text_size =
d.m_text_size;
// no-throw, no-fail
text_size = len;
return true; // Success.
}
bool
input_reader::read_all_the_words_in_the_makako_language
( ::std::istream & is
)
throw()
{ bool ok;
makako_language_reader
reader
( is
, m_data
, m_input_is_not_valid
, m_io_error_occurred
, ok
)
;
if( !ok)
{ return false; } // Failure.
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()
{ bool ok;
::std::ofstream os("abc2.out");
ok = os.good();
if( !ok)
{ return false; } // Failure.
abc2_data & d = this->m_data;
size_t const & number_of_occurrences =
d.m_number_of_occurrences;
os << number_of_occurrences << ::std::endl;
ok = os.good();
if( !ok)
{ return false; } // Failure.
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
/// .
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;
::abc2::input_translation t(d, ok);
if( !ok)
{ return false; } // Failure. Bad input.
(void) t;
::abc2::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