| String matching is extraordinarily useful. In our application, we define the
match quality between 2 strings of lowercase letters to be the number
of positions that match
exactly. For example, the match quality between
"abcdedd" and "bcddd" is 1, since they only match in the 4th character.
We have a string sequence, data, and are interested in finding string sequences
of the same length that fit the data well. We say that one sequence fits the data
better than another sequence if it has a higher quality match with the data at
the first position where the match qualities differ.
String sequences are ordered lexicographically based on the normal alphabetical
comparison between individual strings. That means that if position i is the first
position where 2 sequences differ, the sequence whose ith element would come later
in a dictionary is later in the ordering of sequences.
Given data and candidate return the next later permutation of candidate
that fits data better.
If no lexicographically later permutation of candidate gives a better fit,
return candidate.
|