fork(2) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <limits>
  4. #include <cstring>
  5. using namespace std;
  6.  
  7. // determine how many times the prefix of specific length is repeated in the input
  8. int repetitions(string const & input, int prefix_length)
  9. {
  10. 	int i = 1;
  11. 	while (
  12. 		(i + 1) * prefix_length <= input.size() && 
  13. 		memcmp(input.data(), input.data() + i * prefix_length, prefix_length) == 0
  14. 		)
  15. 	{
  16. 		++i;
  17. 	}
  18.  
  19. 	return i;
  20. }
  21.  
  22. // recursively compress input and return compressed string
  23. string compress(string const & input)
  24. {
  25. 	// recursion termination
  26. 	if (input.empty())
  27. 		return string();
  28.  
  29. 	string best;
  30. 	int best_length = numeric_limits<int>::max();
  31.  
  32. 	// try various prefix lengths
  33. 	for (int prefix_length = 1; prefix_length <= input.length(); ++prefix_length)
  34. 	{
  35. 		const auto max_count = repetitions(input, prefix_length);
  36.  
  37. 		// try various number of repetitions up to the maximum possible
  38. 		for (int count = 1; count <= max_count; ++count)
  39. 		{
  40. 			// the candidate is compressed prefix and the rest of input compressed recursively
  41. 			const auto current = 
  42. 				to_string(count) + input.substr(0, prefix_length) + // compressed prefix
  43. 				compress(input.substr(prefix_length * count)); // the rest of input compressed recursively
  44.  
  45. 			// store candidate if it is better than the currently best
  46. 			if (current.length() < best_length)
  47. 			{
  48. 				best = current;
  49. 				best_length = current.length();
  50. 			}
  51. 		}
  52. 	}
  53.  
  54. 	return best;
  55. }
  56.  
  57. int main() 
  58. {
  59. 	string input;
  60. 	cin >> input;
  61. 	cout << compress(input);
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
ABCABCBC
stdout
copy 
2ABC1BC
https://ideone.com/iKEjea
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!