It looks like you're new here. If you want to get involved, click one of these buttons!
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