  In the Minimum Common String Partition Problem (MCSP), we are given two
strings on input, and we want to partition both into the same collection of
substrings, minimizing the number of the substrings in the partition. This
combinatorial optimization problem has applications in computational biology
and is NP-hard. Many different heuristic and exact methods exist for this
problem, such as a Greedy approach, Ant Colony Optimization, or Integer Linear
Programming. In this paper, we formulate the MCSP as a Dynamic Program and
develop an exact solution algorithm based on Decision Diagrams for it. We also
introduce a restricted Decision Diagram that allows to compute heuristic
solutions to the MCSP and compare the quality of solution and runtime on
instances from literature with existing approaches. Our approach scales well
and is suitable for heuristic solution of large-scale instances.
