Charging Station: Conversions between Patterns and Numbers

Our approach to computing PatternToNumber(Pattern) is based on a simple observation. If we remove the final symbol from all lexicographically ordered k-mers, the resulting list is still ordered lexicographically (think about removing the final letter from every word in a dictionary). In the case of DNA strings, every (k − 1)-mer in the resulting list is repeated four times.