  Motivated by the study of genome rearrangements, the NP-hard Minimum Common
String Partition problems asks, given two strings, to split both strings into
an identical set of blocks. We consider an extension of this problem to
unbalanced strings, so that some elements may not be covered by any block. We
present an efficient fixed-parameter algorithm for the parameters number k of
blocks and maximum occurrence d of a letter in either string. We then evaluate
this algorithm on bacteria genomes and synthetic data.
