string compression in python (looking at repeating substrigs)

Write an algorithm called best_compression(S), in Python, that takes a string S and outputs a minimal abbreviation of S. An abbreviation is constructed by replacing repeated consecutive substrings as follows: if the same substring X appears N times consecutively, then those N occurrences can be replaced by the string (X)N.
Write the best_compression(S) algorithm in a program called stringcompress that prints the best abbreviation of each line read from the standard input. For example, with these two input lines:


The program should output something like this:

Notice that the string xxxxooxxxxo may be abbreviated as (x)4oo(x)4o. However, that abbreviation is not better than the original string, which is also minimal.
i think dynamic programming could work well

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!