Алгоритм подсчета подстрок в числовом диапазоне

Question

Я ищу быстрый алгоритм, который можно использовать для решения этой проблемы: предоставление A и B целых чисел (в диапазоне [0,10^18]) и предоставление списка из N (N < = 1000) числовых подстрок; цель состоит в том, чтобы подсчитать все числа в диапазоне [A, B], содержащем любую из N подстрок. Мы всегда 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. Вычислить возможное количество цифр чисел между А и В. Например между 2 и 2000, количество цифр может быть 1, 2, 3 или 4. С 1 цифрой, необходимо вычислить для номера> 2 и для 4 цифр, вы должны рассчитать числа меньше 2000, то есть начиная с 1.

2. Если число цифр равно k, и вы должны сказать, что находите числа, содержащие подстроку 234, тогда выберите, где вы поместите эту подстроку (по k-2 пути), а затем найдите количество перестановок для всех возможных оставшихся цифр (думаю, в 10^(k-3) способами). Конечно, вам придется дисконтировать для ведущих нулей и т. Д.

3. Повторите это для всех подстрок.

4. Теперь вам нужно будет вычесть те, которые содержат более одной подстроки. Повторите описанную выше процедуру для всех комбинаций подстрок и вычтите ее из вычисленного значения.