algorithm - 查找大数字范围内有多少子字符串的算法

Question

我对这个练习有疑问：

给定一个A到B的范围 ，1 <= A,B <= 10^18
以及一些表示子字符串的整数Ni，其中1 <= i <= 1000; 返回包含任何给定子字符串的 A,B（包括A和B
） 之间范围内的可能数字的总数。

输入

A, B, i 
N1
N2
...
Ni 

例如 ：

简单输入

10 22 2 
1 
10

简单输出

11

解释：从 10 到 22 的范围包含以下数字，10* 11* 12* 13* 14* 15* 16* 17* 18* 19* 20 21* 22包含子字符串 10 或 1 的有效数字标有 (*)

我们如何计算范围内可能数字的总数？

Answer 1

首先，需要了解 Aho-Corasick 自动化以及动态规划。

我们将范围[A,B]的问题分为两个问题[1,B] - [1,A-1]

构建以下动态规划方法。

DP[position][is_equal_to_A][which_node_in_automation];

• 位置表示数字的长度
• is_equal_to_A表示如果现在等于 A 的前缀

然后我们只枚举当前数字的最后一个数字。