Text-shrinking algorithm using dynamic programming

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!

There's a couple of ways to approach this. You could try to find the longest sequences that repeat in the string first and then the next longest (that aren't part of the longer repeating sections). Or you could perform the encoding based on the shortest repeating parts first and then repeatedly run the result back through the algorithm until it stops shrinking. Hmm...

Since you're using brackets [] in the encoding you should consider whether they might also be part of the source string. If so, you will have to "escape" those characters in the encoding.

What about digits? Are those legal source string characters?

First start with the simplifying assumption that all you have to deal with are lower case alpha characters a..z. Then build up from there.

"Or you could perform the encoding based on the shortest repeating parts first and then repeatedly run the result back through the algorithm until it stops shrinking"

That`s a good idea, and it looks like dynamic programming as well. I will look into this concept.

The input string consists only of lowercase alpha characters "a"-"z".
I the output string, each character (digits, "[" and "]" brackets and letters) counts, so the two output strings:
15[a]bc10[a]bc
and
5[a]2[10[a]bc]

are both the best solution for the input:
aaaaaaaaaaaaaaabcaaaaaaaaaabc

This is a run length encoding algorithm and not dynamic programming,