A very long string P is formed by concatenating decimal representation of all numbers from 1 to 1e9. Thus
P = “123456789101112131415161718192021222324252627282930313233343536 … 9999999991000000000”
You are given some query strings, and for each query string Q, you need to find if it is a substring of P.
The solution is based on following ideas:
All strings of length upto 9 appear somewhere in P.
Q does appear in P iff, for some integer a, Q is of the following form and 1<=a-1<a+l<=10^9
Q = (some suffix of str(a-1)) + str(a) + str(a+1) + str(a+2) … str(a+l-1) + (some prefix of str(a+l))
no of digits in ‘a’ can be at most 10, and str(a) starts somewhere among the first 9 positions in Q.
If Q is long enough, there can be at most 45 possible values of a. For each value of a, test if Q is of the above form.
If Q is not long enough, we still know a prefix of str(a) and a suffix of str(a-1). Check if there is a compatible ‘a’.
If |Q| < 10, then Q is always a substring of P. This is because, if
|Q|<=8, then “1”+Q is decimal representation of a number between 1 and 1e9, so it always appears in P.
|Q| = 9 and first character of Q is not ‘0’, then a = int(Q).
|Q| = 9 and all characters in Q are ‘0’, then Q appears in “1000000000”, hence in P.
|Q| = 9 and first non-zero character of Q is at position i. Then a = int(Q[i, 9]) * 10i + 1.
The problem is mainly implementation heavy, so here is psudo code for solution.
Q = input n = |Q| if n<10 return true; if Q=="1000000000" return true; // Q spans over at at least two integers, if at all for offset = 0 to 9 // starting pos of str(a) for len = offset+1 to 10 // length of str(a) if solve(offset, len) return true return false
As one can see, the above code tries to solve the problem for every possible starting position of str(a), and length of str(a). Here is how to solve if Q is “long enough”
bool solve(offset, num_digits) if offset + num_digits > n return solve2(offset, num_digits) // discussed later if offset>=n or Q[offset]=='0' // 'a' cannot have leading 0's return false // str[a, b] is substring of str starting at position a(inclusive) and ending at b(exclusive) a = int(Q[offset, offset+num_digits]) prev = str(a-1) // if a-1 is 0, then offset would be 0 as well (offset< num_digits), so skipped it if Q[0, offset] != prev[prev.length-offset, prev.length] return false while offset < n if Q[offset, min(offset+num_digits, n)] != str(a)[0, min(n-offset, num_digits)] return false; if a>1000000001 return false a++ offset += num_digits num_digits = str(a).length return true
In above code, if the first iteration of while loop is skipped, because it would be “useless”, then make sure that a is 64 bit, otherwise an overflow might happen, as for
Q = “4294967297” + “0000000002”
Now, it remains to show how to solve if Q is “not long enough”.
bool solve2(offset, num_digits) if num_digits == 10 return (Q[0, offset] == ("999999999")[0, offset]) and (Q[offset, n] == ("1000000000")[0, n-offset]) // 'a' can be 10 digit only if a is 1e9 if Q[offset]]== '0' // 'a' has leading 0's return false suffix_of_a = str( 1+ int(Q[0, offset]) )[0, offset] suffix_len = suffix_of_a.length prefix_of_a = Q[offset, n] prefix_len = prefix_of_a.length common_len = suffix_len + prefix_len - n return prefix_of_a[prefix_len - common_len, prefix_len] == suffix_of_a[0, common_len]
You might find that Tester’s and editorialist’s code are shorter and cleaner than setter’s code.