Description
Niflheimr has too many codes in his computer, so he decided to compress some text files to reserve more disk space.
He comes up with two compression method, Run-length and TwoChar encoding.
The rule of Run-length encoding is simple: count the number of consecutive repeated characters in a string, and replace the repeated characters by the count and a single instance of the character. For example, if the input string is 'AAADDDDDDDBBGGGGGCEEEE', its run-length encoding will be '3A7DBB5GC4E', because there are three A's, seven D's, ... etc. Note that we do not need to encode runs of length one or two, since '2B' and '1C' are not shorter than 'BB' and 'C'.
The rule of TwoChar encoding is also simple: given a mapping table which maps TWO Latin character pattern P to ONE non-Latin character token T, then replace all the pattern Pi inside the given string with token Ti. Observe that there might be many ways to encode a string with TwoChar encoding.
Following is an example of TwoChar encoding:
| Pattern | Token |
|---|---|
| AA | * |
| BB | - |
'AABBC' can be encoded into '*-C'.
Now Niflheimr wants you to help him finish the task by implementing
void RleCodec::encode()for Run-length encodingvoid TwoCharCodec::encode()for TwoChar encoding
He will be happy if he can reserve as much space as possible, so for TwoChar encoding, please provide a encoding way which can produce a optimal encoded string, i.e. provide an encoded string with MINIMUM LENGTH possible. He will check the length of your encoded string to judge your solution.
Using the previous table, 'AAAA' should be encoded into '**', 'A*A' is not an optimal encoded string.
For submission, your code may look like the following:
#include "function.h"
// other include if you need
void RleCodec::encode() {
// your code
}
void TwoCharCodec::encode() {
// your code
}
Moreover, choose '-std=c++11' in the compile option while submitting your code to OJ!
In function.h, we add the class DummyCodec as a sample of implementing a derived class of the base class Codec.
Input
First line of input is the string S which will be encoded.
Second line contains an integer N, representing the size of pattern table for TwoChar encoding.
Then for the following N lines, each of them is of the following format:
** -
Where ** is the pattern, and - is the corresponding token.
All the patterns contain only Latin characters, i.e. [A-Za-z], and none of the tokens is Latin characters.
It is guaranteed that all the patterns and tokens are distinct, and the length of the string S is less than 300.
For the first 2 testcases, N == 0. So you can still pass first 2 testcases even if you only implement Run-length encoding!
Output
The first and second lines are RLE encoding and decoding.
The third line prints the length of your TwoChar encoded string. If the length is not optimal, you will get a Wrong Answer.
The fourth line is the result of decoding your TwoChar encoded string. It should be identical to the input string.