<p>You're algorithm has loss of information from compressing the string's original data set so I'm not sure you can recover the full information set without doing far more work than comparing the original string. Also while your data set appears easier for human readability, it current takes up as much space as the original string and a difference map of the string (where the values are the distance between the prior character and current character) may have a more comparable information set.</p>

<p>However, as to how you can detect all common subsets you should look at Least Common Subsequence algorithms to find the largest matching pattern. It is a well defined algorithm and is efficient -- O(n * m), where n and m are the lengths of the strings. See <a href="https://stackoverflow.com/questions/8257655/lcs-algorithm-example">LCS on SO</a> and <a href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem" rel="nofollow noreferrer">Wikipedia</a>. If you also want to see patterns which wrap around a string (as a circular stirng -- where <code>abeab</code> and <code>eabab</code> should match) then you'll need a ciruclar LCS which is described in a paper by <a href="http://arxiv.org/abs/1208.0396" rel="nofollow noreferrer">Andy Nguyen</a>.</p>

<p>You'll need to change the algorithm slightly to account for number of variations so far. My advise would be to add two additional dimensions to the LCS table representing the number of unique numbers encountered in the past k characters of both original strings along with you're compressed version of each string. Then you could do an LCS solve where you are always moving in the direction which matches on your compressed strings AND matching the same number of unique characters in both strings for the past k characters. This should encode all possible unique substring matches. </p>

<p>The tricky part will be always choosing the direction which maximizes the k which contains the same number of unique characters. Thus at each element of the LCS table you'll have an additional string search for the best step of k value. Since a longer sequence always contains all possible smaller sequences, if you maximize you're k choice during each step you know that the best k on the next iteration is at most 1 step away, so once the 4D table is filled out it should be solvable in a similar fashion to the original LCS table. Note that because you have a 4D table the logic does get more complicated, but if you read how LCS works you'll be able to see how you can define consistent rules for moving towards the upper left corner at each step. Thus the LCS algorithm stays the same, just scaled to more dimensions.</p>

<p>This solution is quite complicated once it's complete, so you may want to rethink what you're trying to achieve/if this pattern encodes the information you actually want before you start writing such an algorithm.</p>
Symbolic representation of patterns in strings, and finding "similar" sub-patterns
<p>A string "abab" could be thought of as a pattern of indexed symbols "0101".  And a string "bcbc" would also be represented by "0101".  That's pretty nifty and makes for powerful comparisons, but it quickly falls apart out of perfect cases.</p>

<p>"babcbc" would be "010202".  If I wanted to note that it contains a pattern equal to "0101" (the bcbc part), I can only think of doing some sort of normalization process at each index to "re-represent" the substring from n to length symbolically for comparison.  And that gets complicated if I'm trying to see if "babcbc" and "dababd" (010202 vs 012120) have anything in common.  So inefficient!</p>

<p>How could this be done efficiently, taking care of all possible nested cases?  Note that I'm looking for similar patterns, not similar sub-strings in the actual text.</p>