알고리즘

Question

내가이 exercice에 문제가있는 범위는 얼마나 많은 문자열 큰 숫자에서 찾을 수 있습니다 :

범위 을 감안할를1 <= A,B <= 10^18
및 1 <= i <= 1000와 문자열 Ni를 나타내는 몇 가지 정수와 B에;
는 A, B 주어진 문자열 중 하나를 포함 ( 및 B 포함) 사이의 범위에서 가능한 한 숫자의 수를 반환한다.

입력

예

A, B, i 
N1 
N2 
... 
Ni 

:

간단한 입력

10 22 2 
1 
10 

간단한 출력

11 

,691 363,210

설명 : 다음 숫자를 포함하는 10 내지 22의 범위에서, 문자열 (10) 또는 1 중 어느 하나를 담기 10* 11* 12* 13* 14* 15* 16* 17* 18* 19* 20 21* 22 유효 숫자는 우리가 가능한 수의 총 수를 계산할 수있는 방법 (*)

로 표시된 범위?

Answer 1

먼저, Aho-Corasick 자동화 및 동적 프로그래밍을 알아야합니다.

우리는 [A, B]으로 두 가지 문제 범위 에서 문제를 분할로 [B] - [1, A-1] 다음의 동적 프로그래밍 방법을 구축

.

DP[position][is_equal_to_A][which_node_in_automation]; 

• 위치 그렇다면 우리는 단지 현재 번호의 마지막 번호를 열거

의 프리픽스 이제 동일한 경우 is_equal_to_A 수단

번호

의 길이를 의미한다.