// http://infoarena.ro/problema/abc2
//
// Identific pozițiile candidat, cu ajutorul unui trie.
// Identific o poziție candidat, parcurgând în trie.
// Complexitatea timp este O(M·L)
// , unde M este lungimea textului antic
// , L este lungimea cuvintelor
// .
//
// M ≤ 10 000 000
// , L ≤ 20
//
// , M·L ≤ 200 000 000
//
// , și e o șansă ca timpul de execuție să fie ≤ 0.9 secunde.
//
#include <cstddef>
#include <stdexcept>
#include <string>
#include <iostream>
#include <fstream>
namespace abc2
{
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);
struct abc_node
{ /// \brief The node pointed at by the edge labeled with 'a'.
/// The edge starts from current node.
size_t m_a;
/// \brief Same as before, just that for 'b'.
size_t m_b;
/// \brief Same as before, just that for 'c'.
size_t m_c;
} // struct abc_state
;
/// \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.
size_t m_number_of_words;
/// The length of each word in the Makako language.
size_t m_word_size;
/// \brief The nodes of the trie.
/// The root of the trie is first element in this array.
abc_node m_nodes[maxv];
/// \brief The number of states in the finite automaton.
size_t m_number_of_nodes;
/// \brief The location of the word to add into the trie.
size_t m_word_location;
/// \brief Number of occurrences.
size_t m_number_of_occurrences;
} // struct abc2_state
;
// ______________________________________________________________________________
class node_acquisitor
{ private:
/// \brief The data.
abc2_data & m_data;
/// \brief The location of the acquired node.
/// The acquired node is initialized.
size_t m_location;
public:
node_acquisitor
( abc2_data & data
)
throw()
: m_data(data)
{ acquire(); }
private:
void
acquire
()
throw()
;
public:
operator
size_t
()
throw()
{ return m_location;
}
} // class node_acquisitor
;
void
node_acquisitor::acquire
()
throw()
{ abc2_data & d = this->m_data;
size_t & h = d.m_number_of_nodes;
size_t const i = h;
abc_node * nodes = d.m_nodes;
abc_node & x = nodes[i];
// Increase number of nodes.
// The location of the acquired node is i.
++h;
// Initialize the acquired node.
x.m_a = i;
x.m_b = i;
x.m_c = i;
// Record location.
::std::size_t & location = this->m_location;
location = i;
}
// ______________________________________________________________________________
/// \brief Initializes the trie.
class trie_initializer
{ private:
/// \brief The data.
abc2_data & m_data;
public:
trie_initializer
( abc2_data & data
)
: m_data(data)
{ initialize();
}
private:
void
initialize
()
throw()
{ this->construct_empty_trie();
this->add_root_node();
}
void
construct_empty_trie
()
throw()
;
void
add_root_node
()
throw()
;
} // class trie_initializer
;
void
trie_initializer::construct_empty_trie
()
throw()
{ abc2_data & d = this->m_data;
size_t & h = d.m_number_of_nodes;
h = 0;
}
void
trie_initializer::add_root_node
()
throw()
{ abc2_data & d = this->m_data;
size_t location = node_acquisitor(d);
(void) location;
}
// ______________________________________________________________________________
/// \brief Transition following a labeled edge.
class transition
{ private:
/// \brief The abc2 data.
abc2_data & m_data;
/// \brief The source node.
size_t const m_location;
/// \brief The label of the edge.
size_t const m_symbol;
/// \brief The target node.
size_t m_next;
public:
transition
( abc2_data & data
, size_t location
, char symbol
)
throw()
: m_data(data)
, m_location(location)
, m_symbol(symbol)
{ advance(); }
private:
void
advance
()
throw()
;
size_t &
get_link
()
throw()
;
public:
operator
size_t
()
throw()
{ return m_next; }
} // class transition
;
void
transition::advance
()
throw()
{ size_t & link = this->get_link();
size_t const location = this->m_location;
size_t & next = this->m_next;
if(link > location)
{ next = link;
return;
}
abc2_data & d = this->m_data;
size_t next_location = node_acquisitor(d);
link = next_location;
next = link;
return;
}
size_t &
transition::get_link
()
throw()
{ abc2_data & d = this->m_data;
size_t location = this->m_location;
size_t symbol = this->m_symbol;
abc_node * nodes = d.m_nodes;
abc_node & x = nodes[location];
if('a' == symbol)
{ return x.m_a; }
if('b' == symbol)
{ return x.m_b; }
// 'c' == symbol
return x.m_c;
}
// ______________________________________________________________________________
/// \brief Updates the finite automaton.
class trie_updater
{ private:
/// \brief The data.
abc2_data & m_data;
public:
trie_updater
(abc2_data & data
)
throw()
: m_data(data)
{ update(); }
private:
void
update
()
throw()
{ this->add_word();
}
void
add_word
()
throw()
;
} // class trie_updater
;
void
trie_updater::add_word
()
throw()
{ abc2_data & d = this->m_data;
char * p1 = d.m_words_symbols;
size_t k1 = d.m_word_location;
char * pattern = (p1 + k1); // the word
size_t n = d.m_word_size;
size_t location = 0; // The location of the start state.
size_t i;
char symbol;
size_t next;
for(i=0; n>i; ++i)
{ symbol = pattern[i];
next = transition(d, location, symbol);
location = next;
}
}
// ______________________________________________________________________________
/// \brief Constructs the trie.
class trie_construction_processing
{ private:
abc2_data & m_data;
public:
trie_construction_processing
( abc2_data & data
)
throw()
: m_data(data)
{ build();
}
private:
void
build
()
throw()
{ this->initialize_with_no_words();
this->add_words();
}
void
initialize_with_no_words
()
throw()
;
void
add_words
()
throw()
;
} // class trie_construction_processing
;
void
trie_construction_processing::initialize_with_no_words
()
throw()
{ trie_initializer initializer(m_data);
(void) initializer;
}
void
trie_construction_processing::add_words
()
throw()
{ abc2_data & d = this->m_data;
size_t & word_location = d.m_word_location;
size_t const word_size = d.m_word_size;
size_t const n = d.m_number_of_words;
word_location = 0;
size_t i;
for(i=0; n>i; ++i)
{ // Update trie, by adding the current word.
trie_updater tmp(m_data);
(void) tmp;
// Move the position of the current word.
word_location += word_size;
}
}
// ______________________________________________________________________________
/// \brief Solves the abc2 problem.
class solver
{ private:
abc2_data & m_data;
public:
solver
( abc2_data & data
)
: m_data(data)
{ this->count_number_of_occurrences();
}
private:
void
count_number_of_occurrences
()
throw()
;
} // class solver
;
void
solver::count_number_of_occurrences
()
throw()
{ // Construct the finite automaton.
trie_construction_processing trie_construction(m_data);
// The constructor of trie_construction needs to be evaluated
// , because its evaluation contains side effects:
// it changes the state of the m_data object.
(void) trie_construction;
// Count occurrences, using the finite automaton.
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.
abc_node * nodes = d.m_nodes;
size_t i;
size_t j;
size_t x;
char c;
size_t y;
bool match;
for(i=0; ((m>=n) && ((m-n)>=i)) ; ++i)
{ match = true;
x = 0;
for(j=0; ((n>j) && match); ++j)
{
c = q[i+j];
if ('a' == c) { y = nodes[x].m_a;
}
else { if ('b' == c) { y = nodes[x].m_b; }
else { y = nodes[x].m_c; } // 'c' == c
}
if (x==y) { match = false; }
else { x = y; }
}
if(match)
{ ++h; }
}
// Store number of occurrences, into abc2 data.
::std::size_t & ans =
d.m_number_of_occurrences;
ans = h;
}
// ______________________________________________________________________________
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.
}
// ______________________________________________________________________________
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 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 spaces used by the program.
static
::abc2::abc2_data
s_data;
/// Because the abc2_data is plain old data
/// , so its construction 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::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