Problem 44082. Recycled Numbers (CodeJam Qualification Round 2012)

Let's say a pair of distinct positive integers ( n , m ) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs ( n , m ) are there with A ≤ n < m ≤ B ?

Be careful, it is more tricky than you might first think...