Hint for problem 7.23:

First, note that the subsequences need not be contiguous!
I.e., "ace" is a substring of "abcde".

Instead of using vertex cover, use (the closely related problem)
independent set. 

Given an undirected graph G = (V,E), V = {v1, v2, ..., vn}, 
transform it into the following set of |E|+1 strings:

* v1, v2, ..., vn

* for each edge (vi, vj) in E (i > j), (*CORRECTION!  First leave out
  the larger endpoint, then leave out the smaller endpoint*)

  v1, ..., v(i-1), v(i+1), ..., vn, v1, ..., v(j-1), v(j+1), ..., vn

Now show that v(i1), v(i2), ..., v(ik) is a vertex cover of G
iff it is a common substring of these strings.