danooo
April 9th, 2008, 06:27 PM
Hi,
I am new to this forum and I desperately need an idea of how to solve the following task:
"Write an algorithm which shriks an input string of characters. The shrinking operation consists of replacing a substring "sub" repeated k-times with the following string: k[sub]. The output string has to be the SHORTEST string possible. I should use dynamic programming"
example of an input: "daaaaaaabcaaaaaaabc"
output: "d2[7[a]bc]"
As I said, I am desperated. The biggest hitch is that the resulting string has to be the shortest possible. I tried to think of an idea of how the algorithm should work but i wasn't successful. Most of the ressources I found on the web focus on compression, Huffmal, Ziv-Lempel codes or LCS.
Please help!
I am new to this forum and I desperately need an idea of how to solve the following task:
"Write an algorithm which shriks an input string of characters. The shrinking operation consists of replacing a substring "sub" repeated k-times with the following string: k[sub]. The output string has to be the SHORTEST string possible. I should use dynamic programming"
example of an input: "daaaaaaabcaaaaaaabc"
output: "d2[7[a]bc]"
As I said, I am desperated. The biggest hitch is that the resulting string has to be the shortest possible. I tried to think of an idea of how the algorithm should work but i wasn't successful. Most of the ressources I found on the web focus on compression, Huffmal, Ziv-Lempel codes or LCS.
Please help!