#include <cassert>
#include <cstring>
#include <iostream>
#include <iterator>
#include <string>
namespace
{
template<class It, class C>
It write_rle_run(It d_first, C prev, uintmax_t count) {
if (count > 1) {
*d_first++ = '{';
for (char d : std::to_string(count))
*d_first++ = d;
*d_first++ = ',';
*d_first++ = prev;
*d_first++ = '}';
}
else {
assert(count == 1);
*d_first++ = prev;
}
return d_first;
}
/// aaaab4cpp -> {4,a}b4c{2,p}
template<class InputIt, class OutputIt>
OutputIt rle_encode(InputIt first, InputIt last, OutputIt d_first)
{
if (first == last) // empty
return d_first;
auto prev = *first++; // previous char
uintmax_t count = 1;
for ( ; first != last; ++first, ++count) {
if (prev != *first) { // ended run of the same consecutive elements
d_first = write_rle_run(d_first, prev, count); // write the run
prev = *first; // start new run
count = 0;
}
}
return write_rle_run(d_first, prev, count);
}
}
int main()
{
const char a[] = "aaaa345pp";
char output[sizeof a];
rle_encode(std::begin(a), std::end(a), output);
std::cout << output << '\n';
std::string text = "aaaa345pp";
rle_encode(std::begin(text), std::end(text), std::ostream_iterator<char>(std::cout));
std::cout << '\n';
std::string s;
rle_encode(std::begin(text), std::end(text), std::back_inserter(s));
std::cout << s << std::endl;
std::istream_iterator<char> chars{std::cin}, eof;
rle_encode(chars, eof, std::ostream_iterator<char>(std::cout));
std::cout << '\n';
}
I2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxpdGVyYXRvcj4KI2luY2x1ZGUgPHN0cmluZz4KCm5hbWVzcGFjZQp7CiAgdGVtcGxhdGU8Y2xhc3MgSXQsIGNsYXNzIEM+CiAgSXQgd3JpdGVfcmxlX3J1bihJdCBkX2ZpcnN0LCBDIHByZXYsIHVpbnRtYXhfdCBjb3VudCkgewogICAgaWYgKGNvdW50ID4gMSkgewogICAgICAqZF9maXJzdCsrID0gJ3snOwogICAgICBmb3IgKGNoYXIgZCA6IHN0ZDo6dG9fc3RyaW5nKGNvdW50KSkKICAgICAgICAqZF9maXJzdCsrID0gZDsKICAgICAgKmRfZmlyc3QrKyA9ICcsJzsKICAgICAgKmRfZmlyc3QrKyA9IHByZXY7CiAgICAgICpkX2ZpcnN0KysgPSAnfSc7CiAgICB9CiAgICBlbHNlIHsKICAgICAgYXNzZXJ0KGNvdW50ID09IDEpOwogICAgICAqZF9maXJzdCsrID0gcHJldjsKICAgIH0KICAgIHJldHVybiBkX2ZpcnN0OwogIH0KCiAgLy8vIGFhYWFiNGNwcCAtPiB7NCxhfWI0Y3syLHB9CiAgdGVtcGxhdGU8Y2xhc3MgSW5wdXRJdCwgY2xhc3MgT3V0cHV0SXQ+CiAgT3V0cHV0SXQgcmxlX2VuY29kZShJbnB1dEl0IGZpcnN0LCBJbnB1dEl0IGxhc3QsIE91dHB1dEl0IGRfZmlyc3QpCiAgewogICAgaWYgKGZpcnN0ID09IGxhc3QpIC8vIGVtcHR5CiAgICAgIHJldHVybiBkX2ZpcnN0OwoKICAgIGF1dG8gcHJldiA9ICpmaXJzdCsrOyAgLy8gcHJldmlvdXMgY2hhcgogICAgdWludG1heF90IGNvdW50ID0gMTsKICAgIGZvciAoIDsgZmlyc3QgIT0gbGFzdDsgKytmaXJzdCwgKytjb3VudCkgewogICAgICBpZiAocHJldiAhPSAqZmlyc3QpIHsgLy8gZW5kZWQgcnVuIG9mIHRoZSBzYW1lIGNvbnNlY3V0aXZlIGVsZW1lbnRzCiAgICAgICAgZF9maXJzdCA9IHdyaXRlX3JsZV9ydW4oZF9maXJzdCwgcHJldiwgY291bnQpOyAvLyB3cml0ZSB0aGUgcnVuCiAgICAgICAgcHJldiA9ICpmaXJzdDsgLy8gc3RhcnQgbmV3IHJ1bgogICAgICAgIGNvdW50ID0gMDsKICAgICAgfQogICAgfQogICAgcmV0dXJuIHdyaXRlX3JsZV9ydW4oZF9maXJzdCwgcHJldiwgY291bnQpOwogIH0KfQoKaW50IG1haW4oKQp7CiAgY29uc3QgY2hhciBhW10gPSAiYWFhYTM0NXBwIjsKICBjaGFyIG91dHB1dFtzaXplb2YgYV07CiAgcmxlX2VuY29kZShzdGQ6OmJlZ2luKGEpLCBzdGQ6OmVuZChhKSwgb3V0cHV0KTsKICBzdGQ6OmNvdXQgPDwgb3V0cHV0IDw8ICdcbic7CgoKICBzdGQ6OnN0cmluZyB0ZXh0ID0gImFhYWEzNDVwcCI7CiAgcmxlX2VuY29kZShzdGQ6OmJlZ2luKHRleHQpLCBzdGQ6OmVuZCh0ZXh0KSwgc3RkOjpvc3RyZWFtX2l0ZXJhdG9yPGNoYXI+KHN0ZDo6Y291dCkpOwogIHN0ZDo6Y291dCA8PCAnXG4nOwoKICBzdGQ6OnN0cmluZyBzOwogIHJsZV9lbmNvZGUoc3RkOjpiZWdpbih0ZXh0KSwgc3RkOjplbmQodGV4dCksIHN0ZDo6YmFja19pbnNlcnRlcihzKSk7CiAgc3RkOjpjb3V0IDw8IHMgPDwgc3RkOjplbmRsOwoKICBzdGQ6OmlzdHJlYW1faXRlcmF0b3I8Y2hhcj4gY2hhcnN7c3RkOjpjaW59LCBlb2Y7CiAgcmxlX2VuY29kZShjaGFycywgZW9mLCBzdGQ6Om9zdHJlYW1faXRlcmF0b3I8Y2hhcj4oc3RkOjpjb3V0KSk7CiAgc3RkOjpjb3V0IDw8ICdcbic7Cn0K