用于在数值范围内计数子串的算法

Question

我正在寻找一种可用于解决此问题的快速算法：给出A和B整数（范围[0,10^18]），并给出一个列表N（N < = 1000）个数字子串;目标是计算包含N个子串中任何一个的[A，B]范围内的所有数字。我们总是A < = B，数字子字符串也是[0,10^18]范围内的整数。例1：如果A = 10，B = 22，并给出N = 2个子串= {1,10};计数将是= 11;计数数字：10-> 19和21.

例2：如果A = 175，B = 201，并给出N = 3个子串= {55,0,200};计数将是= 4;计数数字：180,190,200和201.

直接的方法是分析[A，B]范围内的每个整数，但是它不是一个解决方案，因为范围可以是这样的大（直到10^18整数）。

为减少问题的复杂性，我做的第一件事就是从N个子串的原始列表中删除一些无用的子串，例如“没有子串包含在另一个子串中”。例如：{1,10}变为{1}，{55,0,200}变为{55,0}。这不会改变最终计数。

接下来，即使假设我们可以在[A，B]范围内得到一个子字符串的计数，我们仍然无法将此计数与列表中其他子字符串的计数相加，因为一个数字可以包含许多子字符串，而且不应该不止一次计算。

任何想法来解决问题和得到想要的数量？

Answer 1

我认为这更多是一个组合问题。

1. 计算的A和B之间的数字。例如2和2000之间的数字的可能数量，数字的位数可以是1，2,3或4.具有1位，则需要计算数字> 2和4位数字，您必须计算小于2000的数字，即从1开始。

2. 如果数字位数是k，并且您必须说找到包含子字符串234的数字，则选择你要放置该子串的位置（以k-2种方式），然后找出所有可能剩余数字的排列数（我认为以10 ^（k-3）的方式）。当然，你将不得不打折前导零等。

3. 对所有子字符串重复此操作。

4. 现在您将不得不减去包含多个子字符串的字符串。对子串的所有组合重复上述过程，并从计算值中减去它。