Clustering strings inside strings?
Interesting question! I have not encountered it before so here is a solution I just made up, inspired by the approach taken by the word2vec paper:


Define the pair-wise similarity based on the longest common substring (LCS), or the LCS normalized by the products of the string lengths. Cache this in a matrix for any pair of strings considered since it is expensive to calculate. Also consider approximations.
Find a Euclidean (hyperspherical, perhaps?) embedding that minimizes the error (Euclidean distance if using the ball, and the dot product if using the sphere). Assume random initialization, and use a gradient-based optimization method by taking the Jacobian of the error.
Now you have a Hilbert space embedding, so cluster using your algorithm of choice!


Response to deleted comment asking how to cluster multiple substrings: The bulk of the complexity lies in the first stage; the calculation of the LCS, so it depends on efficiently you do that. I've had luck with genetic algorithms. Anyway, what you'd do in this case is define a similarity vector rather than a scalar, whose elements are the k-longest pair-wise LCS; see this discussion for algorithms. Then I would define the error by the sum of the errors corresponding to each substring.

Something I did not address is how to choose the dimensionality of the embedding. The word2vec paper might provide some heuristics; see this discussion. I recall they used pretty big spaces, on the order of a 1000 dimensions, but they were optimizing something more complicated, so I suggest you start at R^2 and work your way up. Of course, you will want to use a higher dimensionality for the multiple LCS case.