// http://infoarena.ro/problema/abc2
//
// Folosesc abordarea descrisă în comentarii.
// Asociez secvențele de lungimea cuvintelor, numere în baza 3.
//
// 3**20 = 3486784401 < 4294967296 = 2**32
// → un int unsigned, pe 32 de biți poate reprezenta numerele
// (20 e lungimea maximă a cuvintelor)
// .
//
#include <cstddef>
#include <stdexcept>
#include <string>
#include <iostream>
#include <fstream>
#include <set>
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);
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 set of numbers associated with words.
::std::set<uint32> m_words;
/// \brief Number of occurrences;
::std::size_t m_number_of_occurrences;
} // struct abc2_state
;
// ______________________________________________________________________________
/// \brief Constructs the set of numbers associated to words.
class words_processing
{ private:
abc2_data & m_data;
public:
words_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 words_processing
;
void
words_processing::initialize_with_no_words
()
throw()
{ ::std::set<uint32> tmp; // the empty set
abc2_data & d = this->m_data;
::std::set<uint32> & words = d.m_words;
// no-throw, no-fail
tmp.swap(words);
}
void
words_processing::add_words
()
throw()
{ // The result:
::std::set<uint32> tmp;
// 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;
uint32 sum;
uint32 digit;
char symbol;
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]; // is one of 'a', 'b', or 'c'
symbol = (symbol - 'a');
digit = (static_cast<uint32>(symbol) );
sum = ((3*sum) + digit);
}
tmp.insert(sum);
// Update position of the current word.
pattern += n;
}
// no-throw, no-fail
::std::set<uint32> & words = d.m_words;
tmp.swap(words);
}
// ______________________________________________________________________________
/// \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
()
{ // 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
()
throw()
{ // 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.
::std::set<uint32> & words = d.m_words;
uint32 msd = 1; // To remove most significant digit.
char symbol;
uint32 sum = 0;
uint32 digit;
bool match;
for(i=1; n>i; ++i) { msd = (3*msd); }
for(i=0; ((m>i) && (n>i)); ++i)
{ symbol = q[i]; // one of 'a', 'b', or 'c'
symbol = (symbol - 'a');
digit = (static_cast<uint32>(symbol) );
sum = ( (3*sum) + digit);
}
if(n == i)
{ match = ( (words.end() ) != (words.find(sum) ) );
if(match)
{ ++h; }
}
for( ; m>i; ++i)
{ symbol = q[i]; // one of 'a', 'b', or 'c'
symbol = (symbol - 'a');
digit = (static_cast<uint32>(symbol) );
sum = (sum % msd);
sum = ( (3*sum) + digit);
match = ( (words.end() ) != (words.find(sum) ) );
if(match)
{ ++h; }
}
// no-throw, no-fail
::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