是否有一种算法可以找到连续数字序列的最短前缀子串的最小集合？

Question

在做任何事情之前，我想先感谢所有过来人的耐心，我没有任何正式的计算机科学背景，所以我可能会错误地使用其中一些术语。

我有一个谜题：给定两个数字，它们定义一组相同位数的连续计数数字，长度大约在 5 到 12 位数字之间（即 50000 和 60000、32325600000 和 32399999999），将其压缩为一组的最快、最有效的方法是什么“包含”后续数字的所有排列的前缀的数量？

我们一直使用的方法是将它们视为数字和字符串的混合。首先删除开头/结尾处所有匹配的 0 和 9 对。其次，创建复制到两列的完整序列，其中第二列始终是相对于第一列删除了最右边数字的子字符串。从那里我可以递归地计算任何给定的一位数较短的子字符串出现的次数，保留 N-count<10 的项目，并且 N-count>=10 从两列中删除另一个数字并重复。

我想知道是否有一种更快、更有效的方法来做到这一点。字符串操作而不是数学是一个明显的快速解决方案，但一般方法仍然依赖于递归分组和截断字符。我考虑过制作一整套前缀和 N 计数列，返回到最高数字，但至少本能地感觉它比在不断减少的数字池上递归操作效率更低。

IE
Input: 
Start=50000000 
End=55399999

which becomes
Start=500 
End=553

Cycle one creates two sequence columns like this:

String   Prefix     N-Count
500        50          10
501        50          10
etc..                  
510        51          10
etc..
550        55          6
551        55          6
552        55          6
553        55          6   

Cycle two keeps everything where N-count<10 the same, but reduces the rest by 1
digit each and recalculates N-count (while getting rid of duplicates).

String   Prefix     N-Count
50        5          5
51        5          5
52        5          5         
53        5          5
54        5          5       
550       55         4
551       55         4
552       55         4
553       55         4  


Output:  50,51,52,53,54,55,550,551,552,553 
```

Answer 1

假设输入是 $a,b$, ， 二 $n$- 长数字。我们允许前导零（我们稍后会看到原因）。让 $c$ 是最长的公共前缀 $a,b$, ， 然后让 $a=cA$, $b=cB$.

如果 $A = 0^{n-|c|}$ 和 $B = 9^{n-|c|}$ 然后我们简单地输出 $c$ （这包括案例 $|c|=n$).

否则，让 $d_A$ 是第一个数字 $A$, ， 然后让 $d_B$ 是第一个数字 $B$.

递归地找到范围的解决方案 $[A,d_A 9^{|A|-1}]$ 和 $[d_B 0^{|B|-1},B]$, ，和前缀 $c$ 对一切。另外，添加 $c(d_A+1),\l点,c(d_B-1)$.

这是一个未优化的 python 实现：

def prefixes(a,b,C=''):
     n, m = len(a), max(i for i in range(len(a)+1) if a[:i] == b[:i])
     c, A, B = C+a[:m], a[m:], b[m:]
     if A == '0'*len(A) and B == '9'*len(B):
         yield c
     else:
         yield from prefixes(A[1:],'9'*(len(A)-1),c+A[0])
         for i in range(int(A[0])+1,int(B[0])):
             yield f'{c}{i}'
         yield from prefixes('0'*(len(B)-1),B[1:],c+B[0])

例如，如果您运行 list(prefixes('50000000','55399999')) 然后你会得到以下输出：['50', '51', '52', '53', '54', '550', '551', '552', '553']