Question 19: Observe that for a given \pi, the length of the correspo…

Based on the above data, answer the given subquestions.

Observe that for a given $\pi$, the length of the corresponding superstring $s(\pi)$, which is obtained by writing the input strings in the order $\left(s_{\pi(1)}, \ldots, s_{\pi(n)}\right)$ and merging adjacent strings, is given by:

$|s(\pi)| = \sum_{i=1}^{n} |s_i| - \sum_{i=1}^{n-1} \left|\text{ov}\left(s_{\pi(i)}, s_{\pi(i+1)}\right)\right|.$

The compression of $\pi$ is the sum of the overlaps of adjacent strings in the permutation $\pi$. Finding a shortest superstring is equivalent to: