Howdy, Stranger!

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

Categories

string compression in python (looking at repeating substrigs)

Simone MasieroSimone Masiero Member Posts: 2

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:

babababbaaaaababbbab
xxxxooxxxxo

The program should output something like this:
b(ab)3b(a)5babbbab
xxxxooxxxxo

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.