用於在數值範圍內計數子串的算法

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. 現在您將不得不減去包含多個子字符串的字符串。對子串的所有組合重複上述過程，並從計算值中減去它。