Алгоритм, чтобы найти, сколько подстрок в диапазоне больших чисел

Question

У меня есть проблема с этим упражнением:

Учитывая диапазон от А до Б с 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

Затем мы просто перечисляем последний номер текущего номера.