encoding.cc.txt

Ulm大学2003-2004年竞赛题

// Problem   Run Length Encoding
// Algorithm Straight-Forward
// Runtime   O(n)
// Author    Walter Guttmann
// Date      2003.12.07

#include <fstream>
#include <iostream>
#include <string>

using namespace std;

ifstream in("encoding.in");

int main()
{
  string line;
  while (getline(in, line))
  {
    for (string::iterator it = line.begin() ; it != line.end() ; )
    {
      int rep = 1;
      while (rep < 9 && (it+rep) != line.end() && *it == *(it+rep))
        ++rep;
      // A sequence of min(rep,9) identical characters starts at *it.
      if (rep > 1)
      {
        cout << rep << *it;
        it += rep;
      }
      else
      {
        cout << 1;
        for ( ; it != line.end() && ((it+1) == line.end() || *it != *(it+1)) ; ++it)
        {
          cout << *it;
          if (*it == '1')
            cout << *it;
        }
        // Either a repetitive sequence begins at *it, or it reached the end of line.
        cout << 1;
      }
    }
    cout << endl;
  }
  return 0;
}